What would be the most (CPU) efficient way to delete address-list via script?
???

Hmm, started writing that before your edit. Yes, I think that's the most CPU efficient method.

I was struggling with getting this to work. Then I realized the list name is case sensitive. FYI

If the list is like >3000 entries, i found that removing the entire list in 1 command will make cpu go very high for a few seconds. So,
can delete them in 255 steps with a 100 ms delay in between. Will push it up to 25 seconds, but CPU will be a lot lower.

This SHOULD work. Remember to change the list name.


{
:for i from=1 to=254 do={
:put "remove $i"
/ip firewall address-list remove [/ip fi address-list find where (list=LISTNAME and address~"^$i\\..*")]
:delay 0.1
}
}

Of course the total amount of CPU time spent will be more in that case, it will be spread over a longer time so it may look less severe in graphs.
It depends on what is your problem. When you have a very old model with 1 CPU (like in 2010 when this question was first asked) maybe there is some impact of running such a long task, but more modern routers have 2, 4 or more CPUs (cores) and it should not matter when you load 1 core to 100%.

Did a test on my RB750Gv3 with an access liste with 8400 ip address, it did take just 5-6 seconds.
Test was to fast done so I did not get any CPU load
So I think that is is not a problem with newer routers.You are going in to this access list if you try to access any port on my router that is not open. You will then be blocked to any port (also open) for 24 hours.
Here is my Splunk app showing number of IP address in the access list going down when I deleted the list. It will quickly grow up again :)

This thread is a bit old, but I just want to say the info here saved me a ton of hassle.

I just deleted a specific IPv6 address list of over 600,000 entries on my router without touching any of the other 10 IPv6 address lists. The code I used was:It took about 10 minutes, but it completed successfully.

Thanks to those who worked on this topic!