For the Arduino Mega part you could pretty much only use the ATMega chip with a few additional component (a crystal, a few resistor and a few caps. As Arduino is open hardware and open source, you should be able to strip off all extra stuff easily.
For the Fona part it's no point stripping that down, only need to solder pins to it.
I would design the whole thing on a breadboard, and after that, design a PCB based on a working schematics.
Edit: Arduino boards come in different shapes and sizes, I recommend you check them all out as the Mega board is huge.