Posting a resolved issue here so that it is more widely known. First post so be gentle!
Attempting to re-program the Mega2560 bootloader using another Arduino as ISP I traced the 'verify error' that many had experienced doing this (using logic analyser to capture the whole 90sec programming cycle and examine the bytes transferred on the target SPI bus), and studying the protocol in detail.
It turns out that avrdude is not setting the 'extended-address' byte, which is required to program a device with >128K of flash. The ArduinoISP uses stk500 (v1) but most devepment seems to be focussed on stk500 (v2), which is very different.
This may be the limitation that lead in part to Nick (Gammon) re-writing the programmer? Anyway there is a fairly small patch to avrdude that I have posted on that mailing list and bugtracker:http://savannah.nongnu.org/bugs/?40897
With this fix, the ISP completes the programming without errors. I think this change would also be necessary to program user code using the ISP (rather than through the bootloader).
Would be interested in others comments, etc.