tutorial for flashing the bootloader?
1) Connect an ISP device to your computer. I recommend the USBasp which you can buy via eBay for less than $4, including shipping! It usually comes with a 10-pin ISP connector and cable. You need to either change one end of the cable to a 6-pin connector or get a 10-pin to 6-pin adapter, also about $4 via eBay. You can't use ArduinoISP for a MEGA because it only does the STK500V1 protocol and the ATmega2560 requires the newer STK500V2 protocol.
2) Connect the ISP device to the ICSP header on your Arduino board. The header on the board should have a marker for Pin 1. The cable usually has a read stripe on the edge connected to Pin 1.
3) Select your board in Tools->Boards
4) Select your ISP device in Tools->Programmers
5) Select Tools->Burn Bootloader