Such a punishment is, in fact, recorded by multiple historians. Our first is Livy, who tells of the consul Appius Claudius. His troops panicked when confronted with a particular challenge and refused to march against the enemy. He hastily punished the most unprepared men, and then drew lots for a tenth of the remainder to be punished. The exact phrasing is:

sorte decimus quisque ad supplicum lecti "each tenth [man] was selected by lot for punishment

Dionysius, who wrote in Greek, also recorded this event, saying it was customary punishment for such offences of cowardice. Other Greek authors who mention it include Cassius Dio, Plutarch, and Apian, in reference to Crassus and Augustus "reviving" an old method of discipline during the Civil War.

Cicero, in his oration on Aulus Cluentius, admonishes administrators for governing by lot in the manner of military punishment.

But what about the actual word "decimate"? It comes to us from the Latin decimo, which is used by two major Roman historians. Tacitus uses it here to describe Galba's cruel execution of men who had surrender to him as he took power:

cum in oculis urbis decimari deditos iuberet "When, in the sight of the city, he ordered those who surrendered to be deimated"

Suetonius also uses it with Galba:

non modo inmisso equite disiecit, sed decimauit etiam "He did not only send them off on horse, but also decimated them."

If you read the full passages, you'll note that nobody really liked Galba. He only reigned seven months in 69 AD ("the Year of Four Emperors") and tried to rework the economy by force, so he his brief reign didn't go over so well.

As you can see, decimation was recognized as a "cruel and unusual" punishment, viewed at first as one reserved for cowards and mutineers, and later as an old military tactic ascribed to cruel emperors.