DaveJJ, you have a number of options regarding performing the brain surgery on your Mega, and gaining the knowledge to do it will just take buckets of reading. You can do it! You might start with checking if your library has books on Arduino, and if they do, check them out and start reading. I don't have footnotes or references like a proper research paper, but here is a glob of stuff I've learned: http://www.instructables.com/id/Overview-the-Arduino-sketch-uploading-process-and-/
Once you know the terms surrounding a particular subject of Arduino, it should make it easier to dig more deeply and research a particular subject area for more details.
Some things specific to the Mega2560 you may find useful:
The Arduino brand Mega2560 uses an ATmega16U2 for its USB to serial chip, as do some other brands, derivatives, or counterfeits. Yours may have ATmega16U2 or may have some other chip, such as a CH340G. It would be good for you to become familiar with which one you have. If you have one with a ATmega16U2 chip, you can use the reference schematic as a guide: https://www.arduino.cc/en/uploads/Main/arduino-mega2560-schematic.pdf
If you have one without the ATmega16U2 USB-to-serial chip, you can probably still use that schematic as a general guide, but you are somewhat on your own when it comes to the USB-to-serial section of the board, and probably also on your own regarding figuring out the power supply section. You may already know this stuff, so sorry if I'm giving redundant info.
You may be able to just cut the reset enable jumper pad, and program the Mega with an external FTDI or FTDI-like adapter and 0.1uF capacitor as DrAzzy suggests. That may be the easiest way to continue using the board. You may or may not need to disconnect the RX and TX lines between the USB-to-serial chip and ATmega2560. If you do end up wanting to do that, the easiest way in my opinion would be to get out an ohm meter and find the 1K resistors which connect the traces between the USB-to-serial chip and ATmega2560, and use a soldering iron to just remove them. That will break the connection.
Depending on what ICSP programmer you have, it may or may not be able to successfully program an ATmega2560 through the ICSP connector. USBtiny and USBasp programmers may not be able to program it. If you read through posts in the Microcontrollers section of the forum you can find a lot of discussion about getting ICSP programmers, especially the USBasp, to work with the ATmega2560, and there is quite a bit of back and forth discussion about memory size limits, firmware upgrades for the programmer, upgrading to avrdude 6.1, fuse bytes for boot reset vector, and so forth. It will be enough to give you a brain workout (or headache). Get caffeinated before reading that stuff.