What I'd recommend is to use an early warning signal. The raw voltage input to the 5V regulator would be a good point to monitor the power. Use this voltage to signal a power failing and if this is set properly, you can get sufficient time to put your counter to EEPROM. Your 5V should be bypassed sufficiently to allow the write to complete.