The Encyclopaedia Judaica, cited in the Wikipedia article linked in the comments above, states as follows:
Eḥad Mi Yode'a is first found in Haggadot of the 16th century and only in those of the Ashkenazi ritual. Many scholars believed that it originated in Germany in the 15th century. Perles showed its similarity to a popular German pastoral song, "Guter Freund Ich Frage Dich" (one of the "Hobelbanklied" German folk songs), the first stanza of which ends with the same words as the Passover song. In fact, the identical words of this line of the pastorale are given as the German translation of the first answer of Eḥad Mi Yode'a in many early Haggadot. The Christian theme of the original was changed to one of Jewish content. Zunz discovered that the Hebrew song was used in Avignon as a festive table song chanted on other holidays as well, and Geiger noted other German counterparts. Since then it has been found among the liturgical music of Jews from Ceylon and Cochin, where it forms part of their Sabbath songs for the entertainment of bride and groom.
Contrary to the EJ's assessment that the Jewish song was preceded by the Christian one and merely derivative, Professors Philip Bohlman and Otto Holzapfel contend in their book Anthology: The Folk Songs of Ashkenaz (pp. 68-74) that the original provenance of the song is less certain:
There is a long history of popular and scholarly speculation about the relation between the Jewish and Christian versions of the song and the extent to which these histories are parallel and probably interacted with each other…. Speculations about which tradition was the original are endless…. In the DVA (Deutsches Volksliedarchiv - the German Folk Song Archive), there are numerous transcriptions for every song landscape…. Noteworthy in each case, however, is the extent to which they exhibit a firm and centuries-old anchoring of the text to specific religious symbolism, drawn from Judaism and, but usually secondarily, Christianity.
R' Yedidya Weil, in his Marbeh L'sapeir commentary on the hagada (1791), mentions a report that this song and Chad Gadya can both be traced to a manuscript found hidden inside a wall in the study hall of the Rokeach (12th - 13th century) in Germany. This article says that the commentary reports that the manuscript was dated to 1406, but after skimming the commentary, I only found two paragraphs discussing this topic, and I didn't find such a date mentioned in either.
The following is from the On the Main Line blog:
[Rabbi Weil] heard that this poem [(Chad Gadya)], along with Echad mi Yodea, was originally found in a manuscript in the Beit Midrash of R. Eleazar Rokeach of Worms (1176 – 1238). Here he does not say anything more about the manuscript, such as its age. However, this Beis Midrash is known to have burned in 1349, being rebuilt during the following five years, and one scholar assumed that if the manuscript existed in the original Beis Midrash then we can say that the song existed in the first part of the 14th century, if not as far back as the lifetime of the Rokeach himself (13th century). However, this is obviously a slender reed (who says it wasn't in the rebuilt Beis Midrash?). Weil writes elsewhere that he used a siddur written in 1406 as a help in writing his commentary. Thus, if this siddur was his source for the statement about Chad Gadya being in a manuscript in the Worms Beis Midrash, we can at least say that in 1406 there was such testimony (I'm given to believe that Rabbi M. M. Kasher discusses this in Haggadah Shelemah, which I didn't see). This of course means that the song was known to exist in 1406.