Speed equals power.
Even a full featured full power chip such as the P89C51RD2 (60 mA at full speed) will use 3 mA or so at 1Hz. When searching for low power chips be sure to find the Icc vs FREQ chart in the data sheet. Of course, if you can go idle (3mA at 6Mhz for above) most of the time, you can save even more power.

In other words, no need to compromise, just write fast code and put it in a slow running processor.

Have fun

Erik