I remember hearing that originally Sanhedrin and Makkot formed one masechta. This is also mentioned by Wikipedia (without citation)
[Sanhedrin] originally formed one tractate with Makkot, which also deals with criminal law.
and is also part of the premise for this question.
What is the source for this assertion? Where is it first attested?
A number of Rishonim quote from Makkot but call it Sanhedrin, implying they considered them to be one tractate. See Ramban to Devarim 21:13 and Rashba to Kiddushin 22a who refer to what we have in the Yerushalmi of the second chapter of Makkot as "פרק בתרא דסנהדרין." Also check out Ralbag to Shemot 21 (Shoresh 4 and 16) who calls our second chapter of Makkot "פרק יג דסנהדרין". (Ralbag also counts them as a single Masechta called Sanhedrin in his introduction to his Peirush on Chumash.)
These are both technically later than the Rambam cited in user6591's answer, but just to add a possibly earlier source, the Midrash Rabbah (Shir HaShirim 6:8 and Bamidbar 18:17) notes that there are 60 tractates [of Mishna], while we have 61 (counting the three "Bava" tractates as one). The Rashash to Bamidbar Rabbah there suggests that this could indicate that Makkot was a part of Sanhedrin at that time. Not an ironclad proof of course, but still worth mentioning.
The Rambam is correct though that there is early manuscript evidence for the joint presentation. The famous Kaufmann manuscript of the Mishna presents Makkot as chapters 12-14 of Sanhedrin. Consider too the incomplete Geonic commentary from the Cairo Geniza (Ginzei Shechter 2 pg 395) which actually combines the chapter אלו הן הנחנקים with כיצד העידם into one long chapter. It's not entirely clear why the Rambam so opposed the notion that they were originally one tractate given all the evidence, the similar topic and style, and the unusual length.
To be fair the Bavli (Shevuot 2b) asks explicitly:
מכדי תנא ממכות סליק מאי שנא דתני שבועות
The teacher just finished Makkot, why is he now teaching Shevuot? (my translation)
but a) that is probably a late addition to the text by the Savoraim, and b) it could just mean he finished the topic of "lashes" from the last chapter of Makkot, not that he finished a work with the title "Makkot".
Rambam seen here in his introduction to his pirush on mishnayos seems to be the first who mentions an opinion like this. Rambam himself however disagreed with this.
אבל מסכת מכות היא נקשרת בנוסתאות עם מסכת סנהדרין ובכללה היא מנויה ואמרו שבשביל שאמר ואלו הן הנחנקין הדביק אליו ואלו הן הלוקין ואין זה טעם אמת אבל היא מסכת בפני עצמה ונסמכה לסנהדרין מפני שאין רשות לבני אדם לענוש ולהלקות אלא השופטים בעצמם כמו שאמר הכתוב (דברים כה) והפילו השופט והכהו לפניו כדי רשעתו.
Indeed, Tractate Makkot is connected to Tractate Sanhedrin in some textual variants, and it is counted as part of it. And they said that because he said, "These are the ones strangulated" [near the end of Sanhedrin], he attached to it, "These are the ones lashed" [at the beginning of Makkot]; but this is not a true reason. [Rather], it is a tractate on its own. And it was made adjacent to Sanhedrin because the only people that have permission to punish and lash are the judges themselves, as Scripture stated (Deuteronomy 25:2), "the judge shall put him down and give him lashes in his presence, by count, according to his evil."
These words of Rambam are brought by Tosafos Yom Tov in his introductory remarks to maseches Makos.
In an anonymous liturgical poem (Azharot) titled "אזהרת ראשית לעמך נתת", predating Maimonides and MS Kaufmann*, the author points to "... six orders of Mishnah, upon which is thirty-six tractates of [Babylonian] Talmud". It reads:
חקרי הלכות וסדרים ששה, ועליהם תלמוד שלשים וששה
This figure can only be possible if Sanhedrin and Makkot are combined (and the three Bavas are counted individually), as follows:
*S. D. Luzzatto (Mavo Le'machzor Bnei Roma, ed. 1967, pg. 52, end) suspects that it dates back to one of the Geonic schools in Iraq. A. Jellinek (Kunteres Taryag, p. 4) opines likes Luzzatto. Eliezer Landshut (Amudei Ha'avodah 313ff.), however, betrays some skepticism by stating that he did not find the poem cited in old texts besides for R. Eliezer b. Nathan.
