Need to power Arduino Mega 2560 with 3.3V
Have you considered maybe using the Iteaduino MEGA2560?

The Iteaduino MEGA2560
uses the same ATmega2560 processor as the Arduino Mega 2560,
but is physically much smaller, the size of a Arduino UNO.
It has a switch to run the ATmega2560 at 3.3 V, so its I/O pins can be directly connected to 3.3 V modules.
It breaks out all the GPIO pins of the ATmega2560,
so it actually has more I/O on its connectors than the Arduino Mega 2560.

If I'm reading this right, the Iteaduino schematics and a typical Iteaduino features list
seems to say it already has a 16 MHz crystal.