The most accurate answer is that we really don't know. We have almost no relevant documentation contemporary with the height Median power, and archaeological work in the relevant areas is comparatively lacking (due in no small part to the Median capital at Ecbatana still being an inhabited city). That said, Assyriologists and Iranists have spent a lot of time theorizing about this in the last 100 or so years, and especially in the last 40ish years with increased comparisons of the classical Greek and Roman sources to actual Near Eastern documents.You asked two distinct questions, so I think the best way to address this is with two distinct answers in three parts
Let's start with what Herodotus actually says about their borders because it is actually extremely vague. Herodotus discusses four Median kings, and the first two are almost entirely ahistorical. Neither they, nor their actions are reflected at all in the Near Eastern records from the time period Herodotus ascribes to them. The first is Deioces, who just founds the Median kingdom around Ecbatana, so let's start with his successor:
Deioces had a son, Phraortes, who inherited the throne when Deioces died after a reign of fifty-three years. Having inherited it, he was not content to rule the Medes alone: marching against the Persians, he attacked them first, and they were the first whom he made subject to the Medes. Then, with these two strong nations at his back, he subjugated one nation of Asia after another, until he marched against the Assyrians; that is, against those of the Assyrians who held [Nineveh] . (1.102.1-2)
As I said, both of the kings mentioned here are not supported by the historical record. The Assyrians make no mention of a Phraortes of Media attacking their capital, and if you follow Herodotus' timeline this would have been happening at the height of Assyrian power in the mid-7th Century BCE, while Herodotus seems to conflate this with the later invasion of Assyria by Cyaxares, who I'll address in a minute. The Assyrians did fight with a Median king around 678 BCE, but he was called Kashtaritu and only controlled territory in Media-proper (ie the northwest of modern Iran). He was also the first person called "King of Media" in recorded history. He certainly did not conquer Persia, which was still Elamite territory at the time, nor did he seize the similarly named Assyrian province of "Parsua" near his own borders. Kashtaritu's kingdom also seems to have petered out after his death or defeat as no other Median kings are mentioned in Assyrian records until their fall. The actual Median Kingdom of the 7th Century BCE was small and brief. Mostly, Kashtaritu seems to have unified a small collection of northern Median cities under his leadership to force the Assyrians out of their territory, and he does seem to have been successful. I'll come back to him later.
Then comes Cyaxares and the Scythians. Honestly, I've tried to write this section four times and just cannot come up with a concise way to go a bout it. Trying to discuss the historicity of anything Herodotus mentions in his supposed period of Scythian rule over the Medes leads to a horrible rabbit whole of trying to explain different bits and pieces. So instead I'm going to try bullet points:
There, the Medes met the Scythians, who defeated them in battle, deprived them of their rule, and made themselves masters of all Asia.
From there they marched against Egypt: and when they were in the part of Syria called Palestine, Psammetichus king of Egypt met them and persuaded them with gifts and prayers to come no further. So they turned back, and when they came on their way to the city of Ascalon in Syria...
The Scythians, then, ruled Asia for twenty-eight years: and the whole land was ruined because of their violence and their pride, for, besides exacting from each the tribute which was assessed, they rode about the land carrying off everyone's possessions. (1.104.2-106.1)
Absolutely nothing supports Scythians (or Medes) anywhere between the Zagros and the Mediterranean at this time. They would have had to interact with two of the most powerful kingdoms in the world at the time (though Herodotus remains blissfully unaware that the Assyrians were still powerful) and pass through Judah without being referenced at all by the Bible. We can safely say this period of Scythian raiding and expansion is fictitious.Now we get to the latter reign of Cyaxares and suddenly most of what happens becomes reasonably historical, but the borders do not. Herodotus writes:
...so thus the Medes took back their empire and all that they had formerly possessed; and they took [Nineveh] (how, I will describe in a later part of my history), and brought all Assyria except the province of Babylon under their rule.
The Medes did in fact take Nineveh under Cyaxares, but once again Herodotus seems entirely unaware of just how powerful Mesopotamia was in this period. Cyaxares allied with the Babylonian king Nabopolassar to conquer Assyria from 616-612. After 612, the Babylonians continued pursuing the Assyrian government to Harran in 609, but the Babylonian record of the Fall of Nineveh says that Cyaxares went home in 612. Interestingly, the Babylonian conquests in Syria and the Levant follow the same basic trajectory as the Scythians described by Herodotus, so there may be some connection between those stories and Scythians or Medes in Nabopolassar's army.What territory Cyaxares got out of this deal is not clear. He did not rule "all of Asia," and he did not rule all of Assyrian territory except Babylon. However, we've already established that Herodotus didn't really understand the extent of the Neo-Assyrian Empire.
What he did understand was specific geographical terminology in his own time. "Assyria" to Herodotus meant roughly the same thing as "Mesopotamia" does to us (via the Romans). In that sense, he may be correct in the geographic terms of the mid-Fifth Century BCE. We don't really know much about the border between Babylon and Media in upper Mesopotamia.On one hand, Herodotus tells the story of the famous Battle of the Eclipse between Cyaxares and the kingdom of Lydia in central Anatolia. There was a real eclipse on May 28, 585 BCE, right in the middle of Cyaxares reign, so the story seems credible. This would imply that Cyaxares' territory bordered Anatolia in some way. Controlling the northern edge of former Assyrian territory would be one way to facilitate that. Many modern maps show the Medes controlling the region around Lake Van in western Anatolia, but contemporary sources and archaeology both suggest that the Urartu (then transitioning into Armenia) was still independent, and centered on the lake. Both contemporary Babylonian and later Greek sources suggest that Cyrus the Great conquered Armenia between Media and Lydia.
The issue is, Nabopolassar recorded campaigns against Urartu in 608 and early Neo-Babylonian records treat Arbela (modern Erbil) as part of their territory. However, by 585 something must have changed for the Medes and Lydians to fight over their bordern in Anatolia. By 530 BCE, Cyrus the Great had seized control of Median territory and apparently controlled Arbela without fighting for it. The Babylonians built a defensive wall, supposedly to defend against the Medes, near modern Baghdad, which was very far south in their territory. It may be that the Medes made incursions and captured Babylonian territory around the Assyrian heartland after 608.
From that we can establish rough western borders by the time of Cyaxares death. Somewhere south of Arbela, plausibly following the Tigris River along a narrow corridor south and west of Lake Van, also forming a border with Urartu/Armenia. The Tigris would account for all of the territory understood clearly as Babylonia, Mede, and Armenian by the time of Cyrus the Great. Then the Halys River formed a natural border with Lydia in Central Anatolia. Of course, Herodotus is our only real source for the stuff about the Halys River, but we have to work with what we have. By the time of Astyages, the borders that Herodotus talks about explicitly seem to be correct, but the general idea of "all of Asia beyond the Halys" is not. Babylon, rather than Media dominated most of the Near East by 6th Century BCE.