According to this article, there were about two million people in Egypt circa 1800 BCE, which is around the middle of the Avot period, and they reached 2.9 million circa 1250 BCE. Professor Natan Aviezer in his essay "The total enrolled in the divisions, 603,550"1 explains the mathematical calculations surrounding the rapid growth of Am Yisrael. Per his calculations, we can see that an eight-generation jump from a small group of 5-10 people to a couple million isn't such a wild thought. The miracle of Bnei Yisrael was one, some or all of the following: None of the children died, every mother had at least six children (above-average), they managed to reach 2-3 million within seven generations (meaning, less than eight).
As to who they were, the answer to that actually fits quite well with the Torah: Egypt was, indeed, divided between different peoples. For many years there were two kingdoms, which fits with the Hebrew name of Egypt, Mitzrayim (מצרים) - plural of metzar (מצר) - two metzarim (שני מצרים), because there were two kingdoms at first.2 At the time, there was much warring between the different kingdoms and groups within the kingdoms. According to Josephus in Antiquities 1:6:2, not much is known about the original families of Mitzrayim because their cities were destroyed in a war with Ethiopia. We see from here that Josephus had information that Egypt was at first divided between the different groups that descended from Mitzrayim. The Patrusim, for example, were probably a group that settled in southern Egypt, as the word Patrosi in Egyptian means "the southern land" (source).
Later, Egypt was unified into one kingdom, but echoes of the divided past of the land can still be found here and there in the Tanach. A few examples:
In Canaan there was a place called "Ma'ayan Mei Naftoach" - this was not long after the Egyptians had lost control of Canaan, so the place was perhaps named after the Naftuchim3.
Egypt was sometimes referred to as "Rahav", which may be a play on Lahav (being that the Egyptians didn't have an L in their alphabet), for example, Tehillim 87:4:
"I mention Rahab and Babylon among those who acknowledge Me; Philistia, and Tyre, and Cush—each was born there."
- Egyptian warriors are referred to as Ludim. For example, Yirmiyahu 46:9:
"Advance, O horses, Dash madly, O chariots! Let the warriors go forth, Cush and Put, that grasp the shield, And the Ludim who grasp and draw the bow!"
It seems, therefore, that the Egyptians in the time of the Avot were mostly comprised of the descendants of Mitzrayim, with one caveat: The Hyksos. The Hyksos were Semitic people that invaded Egypt around the time of the Avot and ruled Egypt for a few centuries. It is unknown whether this group is mentioned under a different name in Tanach or if they appear there at all (here's one view on the matter). It is possible that the Pharaoh at the time of Yosef was so welcoming to Yosef's family because like him, they were Semites and shepherd people (the Hyksos were shepherds originally). Some believe that the sudden change in treatment of Bnei Yisrael by the pharaohs is related to the overthrowing of the Hyksos kings and the return of native Egyptian control of Egypt, and we know from Beresheet 43:32 that the Egyptians didn't quite like the Hebrews.
1 To access it, go to this page, right-click on the title of the essay and select Save Link As, which will allow you to download it.
2 Similarly, Rabbi Yehudah Hachassid said on the verse "And Mizraim begot the Ludim, the Anamim" (Beresheet 10:13) (my translation): "Why were they called in plural form? My father explained that he [Mitzrayim] would only have twins and he would give them the same names, and these are "Ludim", "Anamim" and the rest. And the twins would marry one another, Lud with Lud and Anam with Anam, and for this reason the two twins together were called one nation..."
3 Although some suggest it was named after Merneptah.
