The Arduino Mega 2560 board has EEPROM of 4k, that is index 0 up to 4095. That is okay.
Your sketch has many writes, that will take some time. If the Arduino is turned off while that is being written, it might go wrong.
Because it takes so long to write them, I would certainly add a checksum, to be sure that the data is still okay.
You could add a delay after Serial.begin().
delay(500); // wait for power to be stable
The avr library functions might be more useful.
For example the "eeprom_update_block()" to write a complete block at once.
How do you connect the regulated 12VDC 5A power supply ? To the power jack ? Did you check the voltage regulator ? If might get to hot, and it might reduce the 5V voltage.
If you put your finger on the voltage regulator and you can't keep it on, then it is too hot.
That is why a voltage regulator of 7.5V (or perhaps 9V) is recommended.
When the ICSP programming header is uses (the 2x3 pins next to the microcontroller), the 'avrdude' can be used to write the EEPROM.