What about using the ATmega328 timer. You can have an interruption each 10 seconds or 1 minute, just to check the Relay state, and make the math. It is important to use timers because they are precise. Functions like millis() are not ok for this application.
millis() is implemented with a timer. I don't see the difference. millis() and anything else done with the timers will be as accurate as the system clock.
If it were me, I'd try the following. An RTC could also be used, but most don't have millisecond resolution; whether that is an issue for this particular application I have no idea.
Declare some variables:
unsigned long onTime; //the time the relay was turned on
unsigned long accumTime; //accumulated time the relay has been on for previous cycles
unsigned long totalTime; //total time the relay has been on, including the current cycle
boolean relayState; //current relay state, on or off, i.e. true or false
When the Arduino turns the relay on, capture the time and state:
onTime = millis();
relayState = true;
When the Arduino turns the relay off, accumulate the total time and again capture the state:
accumTime += millis() - onTime;
relayState = false;
Calculate total time on as:
totalTime = accumTime + relayState ? millis() - onTime : 0;