How to keep accurate millis() while using ADC_sleep mode?
Rather than trying to update TCNT0, it might be better to track the number of cycles lost to ADC conversions, and in an intermediate routine – eg, omillis() – compensate for those cycles. [Edit:  See better alternative, below]  

In more detail:

• At each conversion, add about 128·13 cycles (or perhaps 128·13.5, to account for average prescaler delay) to a cycle counter:
 long lostcycles; ...; lostcycles += ADCcycles;

• Within each omillis() call, say return millis()+lostcycles/16000

• Or perhaps say return millis()+lostcycles&gt;&gt;14 to avoid wasting time on a division.  This would be off by 2% on the correction, but I presume the correction is small, say 5% of total time, leading to about 0.1% error because of using a shift instead of a divide.


  Re: “I would miss the overflow event (the one Arduino uses internally for time tracking) every time the ADC conversion is started with TCNT0 > 230” 


That's incorrect [if using suggested approach].  Even if the timer 0 overflow is handled a hundred microseconds late, it will be handled ok. [As noted in Edgar Bonet's comment, a method that just adds to TCNT0 without checking arithmetic overflow, as in original approach, could miss a timer tick.]

Note, the example code using SLEEP_MODE_ADC in the “Sleep during reading” section of ADC conversion on the Arduino on Gammon Forum suggests that one should check for the case where a timer or other interrupt occurs during an ADC conversion.  While SLEEP_MODE_ADC stops clkI/O, clkCPU, and clkFLASH, it leaves Timer 2, WDT, and some other potential interrupt sources active.

A better alternative:

As Gerben points out, it's slightly cleaner to update the count variable maintained by millis(), rather than using an intermediate routine.  For background, refer to his answer to an earlier question.  Here is an adaptation [untested] of the idea to the current case:

unsigned int lostcycles=0;
...;
void accountForADC() {
  enum { ADCcycles = 13*128 + 64;  ms_cycles=16000 }; // adjust appropriately
  extern volatile unsigned long timer0_millis;
  lostcycles += ADCcycles;
  while (lostcycles &gt;= ms_cycles) { // This loop usually runs one pass only
    byte statusReg = SREG; // Save interrupt status
    cli();                 // Turn off interrupts
    ++timer0_millis;       // Need interrupts off for atomicity
    SREG = statusReg;      // Restore old status
    lostcycles -= ms_cycles;
  }
}


After startup, on the tenth call to accountForADC() this code would add 1 to timer0_millis to account for a millisecond lost to ADC conversions. lostcycles -= ms_cycles would set lostcycles to 1280.  After another 9 calls we again add 1 to timer0_millis and reduce lostcycles; and so forth.