A back up battery may be a better way to do it.
This is because the size of capacitor you need to keep the Arduino running while you detect a voltage drop, then perform one or more EEPROM write cycles would be quite large. Without calculating the exact amount of time required to save memory to EEPROM, I’d say you’d need several 1000 uF to maintain the input voltage supply to power the board.
It is important to maintain the 5V supply on the board at all times for a couple of reasons. Changes (especially rapid changes) in voltage supplies can cause digital circuits to do unpredictable things. This is particularly so for EEPROM/FLASH writing routines which rely on generating internal programming voltages and exact timing to inject charges on the gates of storage transistors. This relies on having a stable 5V supply which is hard to guarantee when powering the board using just capacitors.
The only thing worse than losing your data when power fails is the belief that you’ve saved your data only to find that it was corrupted in the process.
The other problem is that measuring an analogue input voltage using the A/D while the 5V supply is changing is not recommended because the number the A/D returns will not be consistent since the internal reference voltage (driven by the 5V supply) is potentially changing in the A/D logic as you make the measurement. Using an A/D cycle to detect the supply voltage dropping also takes many microseconds to perform, which is wasting time you don’t have.
A better way to detect the voltage supply dropping would be to use a voltage divider directly off the input voltage, and have the output of the divider trigger an external interrupt on a digital input pin on the Arduino. The interrupt will react faster than a A/D cycle, and will only happen when the voltage supply drops and can perform a specific routine to save data to EEPROM. Be wary of the time constant introduced by a voltage divider which will make the interrupt detection time slower.
But this alone won’t help if the 5V supply isn’t stable during the EEPROM write process.
The best option might be to also use a battery pack to allow the Arduino to keep running when the input voltage drops, only kicking in when the mains power fails.
If you are using an external wall-wart/brick type power supply to the Arduino (eg 12V DC) you can, for instance, connect a 9V battery with a diode (a 1N4004 will do) in series with the positive lead to the VIN pin on the Arduino, and the negative pin to the GND pin.
The diode stops the battery from supplying current while the 12V main supply remains greater than the 9V from the battery.
When the mains supply falls, the 12V supply will drop to less than 9V, and at about 8.3V the 9V battery will start to conduct through the diode and power the circuit. D1 on the Arduino will stop current from the backup battery from being drained back into the main supply.
This simple circuit will maintain a constant 5V supply to the Arduino.
Perhaps it would be a good idea to also monitor the mains input voltage and alert you some how in the event it fails, since a simple 9V battery probably won’t last too long.
A larger capacity battery can be used for longer life and a different voltage can be used, as long as its voltage is more than 7V and less than the main input DC voltage.
Perhaps you can a combination of the methods I described, ie use a voltage divider to trigger an interrupt that writes data to EEPROM, alerts you then put the Arduino in a low power sleep mode, while using a 9V battery and a diode to keep the power supply happy?