I don't know much about fuse bits and surely not about getting and setting them. As I wouldn't know how to set these fuse bits I'm tempted to think it must have been the bootloader who sets them (wrongly). But when I go through the code I only find boot_lock_fuse_bits_get there seems to be no set function
That avrdude command does NOT upload any bootloader, it merely resets fuses. So, if that repaired it, your problem was not a corrupted bootloader, it was corrupted fuse values.
(Also, I'm not sure why it's uploadable at all, given that you have the serial port connect to both the usb boot port AND your external serial device on D0/D1. If your device was "spewing data", that would surely interfere with bootloading. It's somewhat designed for paralleling two devices, but the external device has to be not driving the MEGA's RXD line during boot (ie "turned off."))
It looks (given that -e didn't do anything, and that you had to use "stk500v2" as the programmer type; avrisp is supposed to be an stk500v1 programmer) like you ended up talking to the MEGA bootloader instead of the AVRISP. It (like most/all bootloaders) ignores fuse settings and chip-erase, and reports success. However, this explains even less WHY what you did fixed your problem!
Fully STK500v2 compatible;
So there are two plausible scenarios. I'd start by researching the compatibility of your programmer with the 2560 chips.
SUPPORTED MICROCONTROLLERS:The following AVR microcontrollers are supported for programming:- Classic 8-bit AVRs- megaAVR- tinyAVR- USB AVR