How do we know there are 613 mitzvos?

The Talmud in Makkos (23b-24a) tells us:

Rav Simlai expounded: 613 mitzvos were transmitted via Moshe – 365 negative commandments corresponding to the number of days in a solar year and 248 positive commandments, corresponding to the number of limbs and organs in the human body. Rav Hamnuna asked: What is a Biblical support for this position? The Torah says “Moshe commanded us the Torah” (Deut. 33:4). The numerical value of the word Torah is 611. Add to that the two commandments that G-d spoke directly to the Jewish people.

Presumably, the number of mitzvos was known by tradition and the verse is merely a textual hint (“asmachta”) to support an already-established fact. (For a fuller discussion of this issue, see the commentary of Nachmanides on the first of the Rambam’s 14 methodologies for selecting what to count as mitzvos on his list.)