Sleep and Millis() - I need both?

You could perhaps use some logic ics to count while you sleep, not sure how much they would draw tho
you can use a clock signal fed into a ripple counter(or multiple for more precision using a faster clock), then get that parallel output into a piso shifter and when the arduino wakes, clock the data in with spi or bitbang it to recieve how many clock cycles have passed since it was asleep