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
mega2560.upload.protocol=wiring
mega2560.upload.maximum_size=258048
mega2560.upload.speed=115200
mega2560.bootloader.low_fuses=0xFF
mega2560.bootloader.high_fuses=0xD8
mega2560.bootloader.extended_fuses=0xFD
mega2560.bootloader.path=stk500v2
mega2560.bootloader.file=stk500boot_v2_mega2560.hex
mega2560.bootloader.unlock_bits=0x3F
mega2560.bootloader.lock_bits=0x0F
mega2560.build.mcu=atmega2560
mega2560.build.f_cpu=16000000L
mega2560.build.core=arduino
mega2560.build.variant=mega
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: AVR® Fuse Calculator – The Engbedded Blog ). 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?