Note the very different addressing 'e0e4' on the dump and '3e0e4'. Is the bootloader simply in the wrong address because of the crappy USBasp programmer?
Mega2560.hex: file format ihexDisassembly of section .sec1:0003e000 <.sec1>: 3e000: 0d 94 89 f1 jmp 0x3e312 ; 0x3e312 3e004: 0d 94 b2 f1 jmp 0x3e364 ; 0x3e364 3e008: 0d 94 b2 f1 jmp 0x3e364 ; 0x3e364 3e00c: 0d 94 b2 f1 jmp 0x3e364 ; 0x3e364 3e010: 0d 94 b2 f1 jmp 0x3e364 ; 0x3e364... 3e0e4: 41 54 subi r20, 0x41 ; 65 3e0e6: 6d 65 ori r22, 0x5D ; 93 3e0e8: 67 61 ori r22, 0x17 ; 23 3e0ea: 32 35 cpi r19, 0x52 ; 82 3e0ec: 36 30 cpi r19, 0x06 ; 6 3e0ee: 00 41 sbci r16, 0x10 ; 16 3e0f0: 72 64 ori r23, 0x42 ; 66 3e0f2: 75 69 ori r23, 0x95 ; 149 3e0f4: 6e 6f ori r22, 0xFE ; 254 3e0f6: 20 65 ori r18, 0x50 ; 80 3e0f8: 78 70 andi r23, 0x08 ; 8 3e0fa: 6c 6f ori r22, 0xFC ; 252 3e0fc: 72 65 ori r23, 0x52 ; 82 3e0fe: 72 20 and r7, r2 3e100: 73 74 andi r23, 0x43 ; 67 3e102: 6b 35 cpi r22, 0x5B ; 91 3e104: 30 30 cpi r19, 0x00 ; 0
Please note that the adafruit usbtiny isp doesn't work with devices over 64K.
Update: The output from my AVRISP2 also seems to start at E000 ... there must be more to this than meets the eye.
After all, you've done nothing obviously wrong here.
I think it probably will fix the problem. There have been quite a few reports of things that work fine on the smaller boards (the Atmega328 ones) which don't work on the larger ones due to addressing issues.
Why does it appear the bootloader is in more than one memory location?
My guess here is that you tried a number of different things (eg. install bootloader from the IDE, install from avrdude) and they failed in different ways (the ways being the incorrect address).