One very strong probable source of the phrase is translations of the Bible.
From Revelation 7:1:
And after this I saw four angels standing at the four corners of the earth, holding the four winds of the earth, that no wind should blow on the earth, or on the sea, or upon any tree.
And again, from Revelation 20: 7–8:
And when the thousand years are finished, Satan shall be loosed out of his prison, and shall come forth to deceive the nations that are in the four corners of the earth, Gog and Magog, to gather them together to the war: the number of whom is as the sand of the sea.
Obviously, these passages were formulated in the days before Earth was widely conceived of (in the Christian world, at any rate) as being spherical. Given a flat Earth, any number of geometrical figures might be used to describe its form; John the Revelator seems to have favored some sort of rectangle, parallelogram, or rhombus.
According to the Wikipedia article on the Book of Revelation,
The bulk of traditional sources date the book to the reign of the emperor Domitian (AD 81–96), and the evidence tends to confirm this.
There were however, two earlier instances of closely related phrases, as rendered in a translation of the Bible from 1851. From Isaiah 12:12:
And he shall set up an ensign for the nations, and shall assemble the outcasts of Israel, and gather together the dispersed of Judah from the four corners of the earth.
According to the Wikipedia article on Isaiah,
One widespread view sees parts of the first half of the book (chapters 1–39) as originating with the historical prophet ["between 740 BCE and c. 686 BCE"], interspersed with prose commentaries written in the time of King Josiah a hundred years later; with the remainder of the book dating from immediately before and immediately after the end of the exile in Babylon, almost two centuries after the time of the original prophet.
which would put the writing of Isaiah 12:12 somewhere between 740 BCE and 609 BCE.
From Ezekiel 7:2:
Also, thou son of man, thus saith the Lord GOD unto the land of Israel; An end, the end is come upon the four corners of the land.
In its article on Ezekiel, Wikipedia notes that "The last dated words of Ezekiel date to April 570 BCE." Clearly, "the four corners of the land" are not coextensive with "the four corners of the earth," but they echo the image of land and earth as four-cornered, and may (if the translation is accurate) provide an imagistic model of earth and land that John the Revelator invoked seven centuries later.