How to build a true ultra low power binary counter
If you're really worried about power consumption you probably have two routes:

1) An FPGA/CPLD-like thing

The Dialog Semiconductor nee Silego GreenPAK stuff has counters built into the fabric.  You probably can't beat it with anything discrete as it has about 1uA of quiescent current.  Your power consumption will be defined by frequency.

https://www.dialog-semiconductor.com/products/slg46127

2) A microcontroller

Most microcontrollers have counters and interrupts built to trigger off their GPIOs and wake the microcontroller up on a pulse or edge.  Some of them may even be able to stay asleep and still run the counter circuitry.

The Ambiq micro stuff is 10uA/MHz.  So, if you run at 1MHz or less, you hit your numbers.
https://ambiqmicro.com/mcu/

However, if you can find a micro that lets your microcontroller sleep and still count, you can probably beat that quite easily.

Hope this helps.