On AVR2650 Datasheet is reported that the typical EEPROM writing time is 3.3ms. But 3.3ms for what? a byte? a word? the whole EEPROM?
That is per byte (erase and write 3.4 ms, only write is 1.8 ms). When writing multiple bytes there are a few clock cycles to be gained by preparing for the next byte during an ongoing EEPROM write. Or even better use an ISR for the EEPROM feed. Not faster but allows some additional processing while a block is written. The largest gain is to have the EEPROM erased before the write (1.8 ms per byte instead of 3.4 ms).
Please see http://www.nongnu.org/avr-libc/user-manual/group__avr__eeprom.html and , http://www.atmel.com/images/doc2578.pdf and table 9-1, pp. 35, http://www.atmel.com/Images/Atmel-2549-8-bit-AVR-Microcontroller-ATmega640-1280-1281-2560-2561_datasheet.pdf.
Cheers!