Did the Romans just borrow the Greek word ταυτολογία and transliterate it as tautologia? Or did they use a different word to express this concept? Furthermore, was the word or concept in common use among the educated class? Do we see it mentioned in any classical or medieval Latin texts?
Let us take a look at a corpus. I found only four hits for tautologia. Quintilianus (Institutio Oratoria 126.96.36.199) says: tautologia, id est eiusdem verbi aut sermonis iteratio. This gives a picture of tautologia as a loan word which does have corresponding Latin terms.
There are more hits for pleonasmos, and it seems to be often spelled with ‑os instead of ‑us. Many appearances of both Greek loan words come across as definitions of a weird foreign word. Some occurrences are not even transliterated.
There is more Latin expression for this, iteratio verborum, and its appearances appear to be more "everyday" usage. It is worth noticing that Cicero only uses iteratio verborum, never the Greek options. You can also replace iteratio with repetitio and verborum with sermonis, but the other options are less popular.
The Greek loan words are certainly possible, but the most idiomatic choice in classical Latin appears to be iteratio verborum, and I imagine one could change verborum to something else if the tautology needs to be specified.
A simple dictionary search (Smith's, in my case) defines 'tautologia' as a repetition of the same meaning in different words, a tautology, with an example given as Marc. Cap. 5, 175.
The Latin for the related idea 'redundance' is pleonasmus (also from the Greek), a use of unnecessary words, which might be said to include tautologies.
The fact that both words appear in reputable dictionaries is already enough to indicate that they were in classical use. No doubt educated Romans would use either, as appropriate, in discussing grammar — in particular, figures of syntax.
[Expanded answer] Tautology and pleonasm are separate figures of speech in English, but often distinguished only pedantically.
'All at once I suddenly did it' is a tautology in which the same thing is said twice, but in different words, all at once and suddenly being of exactly equivalent meaning. In Latin — as in English — tautology may be used for dramatic effect, as when Cicero reports the flight of Catiline with the string of words Abiit, excessit, evasit, erupit.(Cic. In Cat. II, I)
On the other hand, 'he walked on the soles of his feet' is a pleonasm in which, in normal circumstances, the last six words are redundant. A Latin example is Quae postquam vates sic ore effatus amico est. (Virg. Aen. III, 463), where it can be interpreted as a device to adjust the metre.