Is `millis()` affected by long ISRs?
After some digging around in the core, it seems like Arduino updates millis() with a 8 bit timer: it uses overflow with a prescaler value of 64. In simpler terms, it has it set up so a certain piece of code (the ISR) is run approximately once per millisecond on a 16MHz system (and proportionately less frequently on slower clocked systems).

When that ISR is ran, it increments a variable that is used by the millis() function.

So, even if some non-interruptable code is being ran for a fraction of a millisecond, it won't matter since the bit for that interrupt vector will still remain set.

However, there is a problem when the ISR is ran less often than it should be triggered. This may be a result of using noInterrupts() for an extended period of time or when too many other interrupts are being ran and there is not enough CPU for all of the tasks. If a lot of the other ISRs have a higher interrupt priorities, it is possible that the code for the millis() may never be ran. In this case, you would have more serious issues than this, but it is something to keep in mind when you're writing code.

The general rule of thumb of ISRs still apply: keep it short!!!

Note: if you require extreme accuracy, the built in function isn't the best choice. A RTC is a good idea for long term time keeping.