Write to EEPROM during power down
A more sophisticated version of @MikaelPatel's techique is not to store the individual counts, but to store a derivative:


Reserve a block of storage with (say) 8 counters. Each counter has as many bits as necessary to store the largest value - but see below for what "largest" means.
Each time the count goes up, write into the next counter along (modulo the number of counters).
But don't write the value of the counter, write the value divided by the number of counters - counter/8.
Here's the trick: while that looks like you're losing precision, you're not - because the counter location is information too! In fact you're gaining size.


It's best shown with an example. For ease, I'll assume an 8-bit counter, and only 8 counters:

0000: 03 03 03 03 03 02 02 02


Assuming that everything started at 00, that means that it took 8 counts for them all to get to 01, a further 8 counts for them all to get to 02, and only 5 counts to get the first 5 to 03. That's a total of 8+8+5 or 21.

At boot time, look for where the number sequence goes down. That's your current buffer position for future updates, plus the information for the current value:

CurrentCount = [Smaller number] * [Number counters] + [Number of larger];


Once you've worked it out, keep the current value for incrementing, and the buffer pointer for where to store the next count.

Advantages:

A. You write as often as you would storing a counter - but in different locations, spreading the load.
B. Each location (8, 16 or 32 bits) can store a certain maximum - but the total maximum is a factor of Number of Counters larger than that!

Odometer manufacturers use this exact technique to store the current mileage in digital dashboards - they have a legal requirement to maintain the correct number. They only use 16-bit counters (which would overflow after 65,535 miles), but then they use 16 counters, for a total mileage maximum of over a million. Each location only gets written every 16 miles, and they don't need to use 32-bit locations.