all
I have this AVR ISP
https://www.olimex.com/Products/AVR/Programmers/AVR-ISP500/COM11 is from the AVR ISP. The mega was not plugged in when I ran the command.
(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."))
At the time of running the command the mega was no longer connected to the Modem. I was informed that it is dangerous to have the USB connected and the serial port connected at the same time. One reason is that the router is 3.3 volt and the USB is 5Volt. As Mega's are expensive I never did so.
To repeat the story: When I had the problem
Swappped the mega by a UNO => all worked well.
Swapped the Uno for the mega => no more info
Conclusion Mega is the problem => disconnect Mega from rooter and try to find out what is wrong.
Plug mega in USB => port found but no messages on the serial monitor.
Try to upload sketch -> failed
Try to bootload with Arduino ISP failed
Try to bootload using AVR ISP=>failed
Tried the command with stk500v2 instead of stk500v1 => get the advice to use -F
Tried with -F => all works fine again.
(In this process I remember the -e I got advised and added that to)
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!
My AVR ISP document states
Fully STK500v2 compatible;
I understand this as STK500v2 should be the protocol for my AVR ISP. But he; I really don't know what I'm talking about here

.
So there are two plausible scenarios. I'd start by researching the compatibility of your programmer with the 2560 chips.
The documentation of my AVR ISP states the following on compatibility
SUPPORTED MICROCONTROLLERS:
The following AVR microcontrollers are supported for programming:
- Classic 8-bit AVRs
- megaAVR
- tinyAVR
- USB AVR
Someone uploaded a sketch to my Mega with a broken USB port with this AVR ISP so I guess it is compatible but I can't confirm with the above data.
I'm sure I have the new bootloader (uploaded with Arduino ISP) because I tested for the WDT to work. With the original bootloader it didn't work. The red led started blinking rapidly like Lefty described.
Note that I have upgraded the AVR ISP recently so it is running the latest and greatest sotware.
In the mean time I have connected the mega back to the router and it has been working ok for a longer period. I still don't feel comfortable though.
Best regards
Jantje