There are a lot of 'unknowns' here for us.
The 'biggest trouble' with such storage-concepts is taking care of the timeframe while losing power. IF you have 'plenty of warning' about power-fail, so as to avoid update from there-on, you can use any number of NVM options.
The 'easiest option' is to use the RTC-block and Vbat register-file therein as battery-backed storage. Even then you might keep two (vote with 3?) copies to compare to each other. But you might only accept that budget-item if RTC is otherwise useful --- and of course you will lose it all if the battery is pulled or fails...
If you are looking at some form of EEPROM, things get a little more complicated. Firstly write-time, relative to such power-off-notification, is MUCH longer. You may have to assume that the write can out-and-out fail on you. The other factor is overall wearout --- EEPROM is write-cycle-limited, and while you don't give any indication of 'how often' you need to update this count, one approach to 'both problems' is to allocate a 'string' of individually-writable-locations, and set them sequentially to 'zero' at each 'tick event' you are counting, and have a 'group' of these which count each 'significant digit' in a complete 'counter' --- when your 'least significant digit' block is finally 'all zero', clear a zero in the 'next digit block', then if that succeeds erase the whole 'least significant block' and let that digit start-over. At each power-up you just scan the least-block to find the 'next virginal location' and that will be your 'next to be zeroed'. In this way you have divided the 'wear' by the number of items in a block, AND if any individual write is 'corrupted', you will either 'still see it erased' OR in some interim non-erased state, and either way should give you a 'valid enough' count of total cycles that have elapsed.
