If a conquest happens shortly enough before the region becomes literate, legends of the conquest may be written down after literacy begins, and then later historians can dispute forever whether that legendary conquest in preliterate times actually happened.

For example, according to later legend King Harald Fair Hair conquered all the other kingdoms in Norway and united it about 872. But a number of skeptical modern historians doubt whether Harald did unite Norway and even if he existed.

Another legend claims that a man named Nor conquered and united Norway and that most of the kings of the small kingdoms in Norway that were conquered by Harald Fair Hair were descendants of Nor.

https://en.wikipedia.org/wiki/N%C3%B3r1

Since Norway was inhabited for thousands of years before its recorded history began, it is certainly possible that it was united and later divided, united and later divided, a number of times before recorded history, and that the legends about Nor and Harald Fair Hair - if true - merely refer to the last two instances.

The list of Inca rulers goes back to Manco Capec (ruled 1200?-1230?) and the small Kingdom of Cuzco expanded to become the Inca Empire and probably the largest native realm ever in South America during the reigns of Pachacuti Inca Yupanqui (r. 1438-1471/72) and his successors. There were many civilizations in South America before the Inca Empire, and a number of strong and powerful states.

Fernando de Montesinos's history of Peru (1644) has a list of Inca emperors far longer than the usual 12, a list of 104 or 107 monarchs.

Some scholars believe that these represent a pre-Inca sequence of Andean lords going back to the Wari or Tiahuanaco states.

https://books.google.com/books?id=6Wa9RwqdqEkC&pg=PA45&lpg=PA45&dq=inca+chronicle+of+montesinos&source=bl&ots=hKZJ7YuURg&sig=ACfU3U1syRGMe10JbSLU2T4jCJnUTVrhmg&hl=en&sa=X&ved=2ahUKEwiX7YSa45jgAhWXxIMKHf8ZDzkQ6AEwAnoECAcQAQ#v=onepage&q=inca%20chronicle%20of%20montesinos&f=false2

Thus it is possible that the list may include the names of rulers of large conquering empires otherwise forgotten by history and with little evidence to connect to various states shown to exist by archaeology.

A hundred rulers with 5 to 30 years per average reign would have spanned 500 to 3,000 years if the rulers were all sequential and didn't include rulers of different states reigning at the same time.

Since the foundation of the Chinese Empire in 221 BC the Chinese realm has often broken apart into several separate states and later been reconquered and reunited by one of those states. Sometimes part or all of China proper has been conquered by foreign peoples and other times China has conquered many foreign lands. Thus the borders of China have constantly expanded and contracted.

The earliest known Chinese writing dates back to the Shang Dynasty, the first historical dynasty of China. The Shang Dynasty (c. 1600 BC-c. 1046 BC) kingdom was probably comparatively small compared to all of China. And it is natural to suppose that the legendary first dynasty, the Xia Dynasty (c. 2070 BC - c. 1600 BC) - if real - ruled the same or a smaller area than the Shang Dynasty, and that the legendary earlier Three Sovereigns and Five Emperors that ruled China - if real - ruled the same or a smaller area than the Xia and the Shang.

But it seems possible to me that some of the legendary earlier rulers may have conquered, united, and ruled a vast area for an unspecified amount of time, and than later rebellions reduced the size of the state to a comparatively small size during the Xia Dynasty. This may have happened two or more times between the earliest of the Three Sovereigns and Five Emperors and the Shang Dynasty.

Thus some legends that legendary early rulers of some lands ruled areas much larger than those lands were in historic times could possibly be based on actual vast but short lasting prehistoric conquests.

Dead bodies!

Seriously, preserved remains with markers of violence are the one side, the weapons used for that and obviously also fortifications the other:

There seems to be general agreement that there is little sign of conflict in Southeast Europe during the Mesolithic and Neolithic periods. In contrast, the incidence of skeletal damage found among Mesolithic burials in northern and western Europe suggests that violence was a regular part of life, particularly in the Later Mesolithic, due perhaps to pressure on resources. Among the LBK farmers of central Europe there seem to have been episodes of extreme violence in which whole communities may have been massacred. In Neolithic western Europe some enclosed settlements were apparently attacked and their inhabitants killed, and some collective tombs included individuals who had suffered violent death.

Violence, therefore, was present in the early periods of European prehistory, but it is difficult to characterize; sporadic flare-ups generally seem more likely than the organized and institutionalized violence of warfare. There seem to have been no objects designed solely for attacking people; domestic tools and hunting weapons were used to inflict the injuries that have been identified. Nor were settlements generally defended against human attack, although the ditches, banks, wooden palisades, and stone walls used to demarcate settlements and keep animals in or out could also offer protection when violence erupted.

From the Chalcolithic period onward, however, the evidence suggests conflict was becoming both expected and managed. Sites in many parts of Europe, from the steppe through the southeast into central Europe and in the western Mediterranean, now had more businesslike defenses. Objects per- haps specifically designed as weapons, such as battle-axes, were now appearing, and the Beaker emphasis on archery equipment suggests that suitable tools were also being promoted as weapons. Individuals, particularly males, were regularly buried with such equipment, showing that being a warrior was now among the social roles marked in funerary ritual.

But there is one caveat for answering this question: the Alexander-style scale of conquest was extremely rare. If ever approaching that type of conquest. Warfare being more often on the scale raiding parties.

Although warfare was endemic in Iron Age society, much of it was on the level of raids to acquire booty, cattle, and women, as well as slaves to supply the insatiable requirements of the Mediterranean world. Successful raids required mobility; chariots, horses, or boats were essential to make the attack swift and unexpected and to evade pursuit. Raiders were therefore generally a select band of nobles and their personal followers.

Jane Mcintos, Handbook to Life in Prehistoric Europe, 2006

Linguists can offer some insight. In The Horse, The Wheel and Language, the spread of Proto Indo European languages, along with accompanying technology, helps explain what might have been a series of invasions.