When did Jews start reciting the Shema Prayer?
Was it before or after the Babylonian Captivity?
Was it before The Exodus?
Did Moses start the practice?
A well-known midrash (Devarim Rabba 2:25) says that Jacob said the Shema before his death, according to which it would have been from before the exodus. The text itself is in a speech attributed to Moses. Of course, even without questioning the historical reliability of these sources, neither of them tells us anything about whether the Shema was used as a prayer.
The Bible gives no indication that it was used as a prayer. To my knowledge, one of the earliest sources is the Mishna (Tamid 5:1) which says about the priests in the Second Temple:
אמר להם הממונה, ברכו ברכה אחת, והן בירכו. וקראו עשרת הדברים, "שמע" (דברים ו,ד), "והיה אם שמוע" (דברים יא,יג), ו"ויאמר" (במדבר טו,לז)...
The appointee told them to recite one blessing, and they blessed. And they read the ten commandments, shema, vehaya im shamoa, and vayomer...
This is quoted in Berachot 11b, which debates which blessing they recited, and tells us that they didn't recite ten commandments outside of the Temple because of a dispute with heretics.
Apart from this source, the houses of Hillel and Shammai, from Temple times, debate how to recite Shema (Berachot 1:3). Rabban Gamliel, Rabbi Eliezer, and Rabbi Yehoshua, all who lived immediately after the destruction of the Temple (70 CE), are also mentioned.
Josephus, also their contemporary, also mentions its recitation twice a day (Antiquities 4.8.13):
Let every one commemorate before God the benefits which he bestowed upon them at their deliverance out of the land of Egypt, and this twice every day, both when the day begins and when the hour of sleep comes on.
In short, the earliest historical sources date to the end of the Second Temple. If it was recited earlier than then, it was either not used as liturgy, or simply not discussed.