The earliest literary description of an army marching in step is Thucydides' description of the advance of the Spartans at the battle of Mantineia, 418 BC:

After this they joined battle, the Argives and their allies advancing with haste and fury, the Lacedaemonians slowly and to the music of many pipers—a standing institution in their army, which is not for the sake of the god, but so that they advance walking evenly and in time, without breaking their order, as large armies often do when they go into battle.

-- Thuc. 5.70

That said, the Spartans probably weren't the first to invent it. Just a few decades after Thucydides completed his work, the Athenian mercenary commander Xenophon completed his account of his service in Persia, in which he described the advance of his Persian and Egyptian opponents at the battle of Kounaxa in 401 BC:

As for the statement which Kyros made when he called the Greeks together and urged them to hold out against the shouting of the barbarians, he turned out to be wrong; for they came on, not with shouting, but as quietly and calmly as possible, advancing evenly and slowly.

-- Xen. Anabasis 1.8.11

It seems extremely unlikely that the Egyptians and Persians picked this up from the Spartans, whom they had not encountered in battle for decades. Instead, it would have emerged from the Near East's indigenous heavy infantry tradition, which was longer than that of the Greeks; many Mesopotamian empires had heavily armoured spearmen of some sort in their armies, and reliefs from the region strongly suggest that these spearmen knew how to march and fight in formation. Indeed, the famous Stele of the Vultures suggests that the Sumerian city-states had something strongly resembling a phalanx as early as c. 2400 BC, nearly two thousand years before such a formation was first seen in Greece. While we cannot be sure that these stylized images corresponded with the reality of heavy infantry fighting, the sheer number of such images especially from the Neo-Assyrian Empire (10th-7th century BC) implies a well-established fighting style.

Greek hoplites, being amateur warriors from states with little coercive power, were late and only loosely organised exponents of a wider Near Eastern tradition of fielding armoured spearmen. Only the Spartans ever properly learned to march in step, which most other Greek states never bothered to pick up. The Greeks only loom large in our early evidence for such practices because they did not universally adopt it; this fact forced their historians to describe it in detail to their ignorant readers.

Like the older empires of the Near East, the more powerful Greek kingdoms of the Hellenistic period were able to field more professional heavy infantry that operated in tightly organised formations. These troops would not be able to function without proper formation drill, and would have marched in step both on the march and in battle. These armies proved totally superior to the militias of Greek city-states - but they proved too expensive to maintain, and by the end of the Hellenistic period the sophistication of their battle drill had become an antique marvel for armchair generals.

The point here is that marching in step was not simply invented once and then universally adopted. The practice almost certainly dates to an irrecoverably early time in Mesopotamian history, but it fell in and out of use depending on the professionalism of armies and the degree to which they focused on organised heavy infantry fighting.