The RP5C01A real time clock has two modes of operation:
Operating and backup.
With a supply voltage of 5.5-4.7V it's in operating mode, draws significantly more current (250µA) and can be communicated with via the address/data bus.
If the supply voltage falls below 4.7V, it switches to low current (15µA) backup mode, where only the crystal oscillator and an internal counter runs in order to keep the time/date.
So to answer your question, the battery voltage at the RTC input (pin 18) must be between 4.7V and 2.2V for it to run in backup mode and without loosing data.
An easy solution for you would be to use 3 x Ni-Cd or Ni-MH cells in series. Either AAA, AA or whatever. That will give you a nominal terminal voltage of 1.2 x 3 = 3.6V.
This is exactly what's in most cordless phones. The batteries are rechargable, so no modifications to the board are necessary.
I've written a guide for replacing batteries as well as using alternativcordless phone battery types:
http://amiga.serveftp.net/battery.html