At the time of THE TRIAL OF A TIME LORD the sixth Doctor states "10 million years of absolute power that's what it takes to be really corrupt", we may therefore take that as a description of the minimal length of Time Lord Civilisation. But it could actually have been much longer: the ten million years could refer only to that particular administration, or to the specific period of power when the Time Lords felt absolutely unassailable, or to the period that excludes 'the dark times' also known as the 'rassalonic era', or even just how long its been since the Doctor was last there.
It is more likely that the Time Lords were powerful for billions of years.
We know that the Time Lords contended with the Racnoss [together with the so-called fledgeling empires (ie just born, and 'learning to fly' by metaphor)] 4.2 billion years ago [when the Earth was forming].
The Time Lords have diplomatic ties with the Third Zone Governments [the Two Doctors] which are contemporaneous with 20th century earth. In the Three Doctors, Omega's energy drain assault on the then unnamed planet of the Time Lords seems to co-incide with his sending creatures to kidnap the third Doctor from Earth (in the 20th century).
The most likely answer therefore is that the Time Lords were powerful for at least the last 5 billion years, but that they were ''absolutely' powerful [having complete mastery of time/space travel ie TARDISES, not time-scoops, and with Gallifrey shielded by transduction barriers from any possible physical attack. So secure that they could forget their own origins] only for the last 10 million years.
[Actually the shows writers never defined the answer, but the above connects the greatest number of dots. The position that the Time Lords were a civilisation of the far past existing to the present day, was also the position taken in the licensed New Adventure books published by Virgin Publishing, and in the recent licensed tie-in book "A brief history of Time Lords".]