EEPROM with high endurance

Another solution could be to use a microcontroller with non-volatile FRAM. FRAM doesn't suffer from the same limitations on write cycles as EEPROM.

Some of the MSP430 products from TI are available with FRAM, here's a link to an application similar to what you describe:

MSP430 with FRAM save state on power failure

Here's the Wikipedia article on FRAM: FRAM

I have this issue in a current project.

The way I'm dealing with it is to keep the live value of the counter in RAM. I added a little bit of hardware so that the microcontroller can detect that the raw input power voltage is low. If so, it stops what it's doing, saves the live counter value in EEPROM, then waits watching the raw power voltage. If it goes back up, with some hysteresis, then the micro essentially restarts. Otherwise, if power continues to go down, the micro will eventually get stopped. On the next restart, the counter value is loaded from EEPROM, then used live in RAM again until the next power-down.

It doesn't take long to write a small value to EEPROM. Most likely your existing power supply system has enough energy storage that you can detect the voltage going low, and still have enough guaranteed run time before power to the micro goes below the operating or EEPROM write threshold.

In my case, the only additional hardware was a Schottky diode to prevent the DC power supply from sucking charge from the local reservoir on the way down, and two resistors as a voltage divider so that the micro can read the raw input voltage. The rest is firmware.

It's important to note that you should be watching the voltage on the input to whatever final supply powers the micro, not the micro's power voltage directly. By the time the latter goes low, it may be too late. Hopefully there is a voltage range that is below the worst case when everything is operating correctly, and above what the micro's power supply needs to guarantee regulated voltage to the micro. In my case, the micro's supply was a buck regulator fed from 48 V, so there is a large range that is below normal but where the micro can still operate reliably.

Old old old solution, cmos counter + lithium battery or Ram + lithium battery.

The power supply for the storage element comes from the normal power supply when it is available or the battery when it is not.

A lot of modern micros in sleep will maintain their state with a very low current supply. So you can use this technique with power down detect to go to sleep then use a battery to maintain state during the sleep period while the main supply is off.