The Arduino MEGA runs at 16 MHz clock; the CKDIV fuse bit is un-programmed (Low Fuse Bit setting is 0xFF). The MEGA can only be slowed down if some has played with the System Clock Prescaler Register (CLKPR). The CLKPR is a non-volatile EEPROM type register; once its value is changed, it remains there until it is altered again.
You please, read the value of the CLKPR Register, and the content should read 0x00 (see chart below) for the MEGA to run at 16 MHz.
In case, you find different value (which I seriously suspect from your description), you can reprogram the CLKPR register in the light of the following example.