Is it possible to run the atmega2560 at 3.3V with the Arduino software on a custom board?
Yes... the Mega2560 can run at 3,3V, you must however be sure that the crystal is 8MHz and not 16MHz as that is out of spec for this chip.
According to the datasheet from Atmel the ATmega2560 is rated for 4.5 to 5.5V only.
The ATmega2560V is a version that supports lower supply voltages, and would only run at 8MHz at 3.3V.