It seems that there's an issue in the memory reserved for the bootloader on the Arduino MEGA2560 boards.
This is the entry in the boards.txt:
mega2560.name=Arduino Mega 2560 or Mega ADK
As you can notice, the entry tells the IDE that it can use up to 252K of Flash for the user's sketches, so that the bootloader space is only 4K:
256K => 262144b
262144 - 258048 => 4096b
But you can also notice that the high fuse, that sets the size of the flash for the bootloader, reserves 4096w (words), that are 8192b (bytes). Its value is $D8 (As you can see using this tool: http://www.engbedded.com/fusecalc/
). The page for the Arduino MEGA2560 says: "Flash Memory 256 KB of which 8 KB used by bootloader". So the size set by the fuse should be right. So, why the entry tells the IDE that it can use up to 252K?