RTC - is it worth it?
Firstly, a real time clock is not what you want.  A real time clock is designed to give you the current time, as in year, month, day, hour, minute, second etc. It usually has a battery, so it can keep track of time when the device is switched off, and will be much more complicated than a basic timing device.  You want to measure relative time, not absolute time, so you need an oscillator.

So you have a few options:


Use the internal oscillator in the AVR, as is. Most (all?) ATmega series chips come from the factory with an internal oscillator which is accurate to about ±10%.
Use the internal oscillator, but calibrate it first.  You can measure the frequency of the internal oscillator, and adjust it by writing to the special variable OSCCAL.  You will end up with a oscillator which is stable to about ±0.3% but depends slightly on the temperature and supply voltage.
Use an external crystal oscillator. Actually, if you are using an Arduino, there is one built into the board.  The accuracy will depend on the oscillator and how much you pay for it, but typical is 20ppm (ppm = parts per million, 0.1%=1000ppm). Expensive crystals can be a thousand times better than that.


Any of the above will give the MCU a time reference, and you then need to write some code to measure time using that reference.  millis() is a good start but you'll get slightly better accuracy using the AVR's built in timers.