The sources are vast, ranging from the Tanakh itself, through Tannaitic and Amoraic eras, and into the Geonic era (since you specifically asked for sources pre-rishonim).
The Shema (Devarim 6:4) is of course the flagship statement of Jewish monotheistic faith (see also Devarim 4:35 and others).
See also Yeshayahu 44:24 and 45:12; Tehillim 135:6; Daniel 4:35; and others.
As for the talmudic sages, see tractates Sanhedrin and Hagigah. There is alot of material here, so do some searches.
The apex that will include everything that has come before it are geonic works such as HaNivhar Emunoth wa-Deoth by Rav Saadyah HaGaon and Hovoth HaLevavoth by Rabbenu Bahya ibn Pequdah (particularly in the section Shaar HaYihud).
In short, the source for the specific ruling of the Rambam is traditionally attributed to Mishnah, Sanhedrin chapter 10. As for the rationale of his ruling, Jews have historically written about it, but have usually chalked it up to the conclusion of logic and common sense.
Hope this helps. Kol tuv.