You're looking at replacing the microcontroller itself.
Comparable to pulling an atmega168 out and putting in a 328.
Am sure its doable if you comfortable unsoldering the 1280 and can do so without damaging the pads to install the 2560.
The parts are listed on the same atmel datasheet.
I haven't compared the 2 schematics to see if anything else would need to be done.
Wow - $18 for the 2560!