Please see Devarim 7:7. How can Moshe say the Jews were the fewest? There were 601730 men between 20 and 60. That’s quite a large population. For the Jews to be smaller than all the other nations there would need to have been over 21 million people in Israel and over 9 million people among Moav, Ammon and Edom.
The commentator Rashi explains that the reference is not to numbers, but to estimation:
you regard yourselves as small, as, e.g., Abraham did who said, (Genesis 18:27) “For I am dust and ashes", and as, e.g., Moses and Aaron did who said, (Exodus 16:7) “And we, what are we?".
What did Moshe mean in Devarim 7:7 by we (Jews) are few in number?
For a short answer: Yes. We were fewest among the nations. But Abraham’s descendants will be as numerous as the stars.
I am convinced that the Bible always, not just sometimes, exaggerates numbers to make an impact. I think the total number of Israelites that left Egypt with some Egyptian spouses were far less than 600,000.