Note that writing EEPROM is slow - on the order of milliseconds per write - which may limit the performance of your sketch.
A better technique is to provide a limited backup power supply to the MCU; enough to complete a set of EEPROM writes + a safety margin. A capacitor could possibly provide enough run time if doesn't have to power much else. Then, detect and interrupt on a failure of the main supply, immediately write your backup data to EEPROM, and enter an infinite loop to wait for the backup supply to fail. When the system resets, examine the EEPROM to be sure there is valid backup data there, restore what needs to be restored, and resume your task.
Update:
A search for "arduino backup power" finds a number of articles related to switching an Arduino from mains power to battery power when the mains fails. You would only need a very small battery if you're willing to only save necessary information then shut down until the power returns. A capacitor might keep your MCU running long enough to do that. Designing the circuit depends on too much we don't know about your system, though.
In fact, simply switching a backup battery as some of these articles describe, or better, running on a battery which is kept on a mains charger, may make a much simpler system that can surviVe reasonably long power outages without shutting down. Again, we don't know how often or how long your power goes out, and how reliable your system is required to be.