There are mythical accounts verbally communicated for geological events like mega eruptiona spanning tens of thousand years.
See, thats the fascinating thing about crackpot archeology/anthropology/sociology/etc. Eventually, its just a bunch of words - an ontology - with which to describe a complex system.
The idea that the root nature of the language is expressible in human-ideal objects, and that this ontology can persist across 10's of thousands of years of human activity (mostly destructive) as a cultural artifact with a message .. yes, this is difficult to conceive. Or, is it really?
"Far-fetched empires": literally what it means to consider what such an empire, were it in existence 65,000 years ago, would have looked like. Like, literally, its a far-fetched idea to look at a piece of dirt, and then paint a deep picture of what happened to it.
Without such imagination, speculation doesn't begin, and without speculation followed up by careful inspection, the relics would still just be out there, being ignored.
I'd speculate that since language skills are important, evolution would have worked to increase them over that era.
That is a meaningless statement, when there is no consensus on the fundamentals of language, and more so because the Languages of the world differ variously.
I'm not sure what you think how complexity of language is measured. Certainly, there are terms and expressions that had to be invented along with the concepts that they describe, which hunter gatherers don't know, and that's not limited to technology. Emotional content would be much more important on a human scale. I think the question would have to be, whether everyone was able to speak. Which term would the analogous to "literate"?
The only way I can think of for measuring the complexity of a language is an inaccurate empirical one: see how hard it is for speakers of unrelated languages to learn it. That approach would probably confirm that Hausa is harder to learn than Bahasa Indonesia, for example, though whether that's what other people mean by "complexity", I can't say.