I finally got an ATmega2560, and therefore went and updated my Bus Pirate extensions to support memory paging on it. The fix wasn’t too extensive, just a matter of having some hardware on hand to test it.
I have also gone and updated all the avrdude and buspirate patches to support the latest versions of both (avrdude 5.11 and buspirate 6.1 r1676).
The details can be found in my original blog post about this at http://coding.zencoffee.org/2011/08/bus-pirate-40x-verify-speed-increase.html
If you use it, let me know how you go!