Moshe was 80 when he approached Par'o before the makos, and the makos lasted a year, so he turned 81 in the Adar before the Jews left Mitzrayim. As he turned 120 in the Adar before the Jews entered Israel, the Jews were in the desert only 39 years. What gives?
Seder Hadorot tells us that Moshe Rabbeinu was born in the year 2368.
It then tells us that G-d spoke to Moshe at the burning bush on the 15th of Nissan in the year 2447. This would mean that Moshe had just turned 79 a little over a month before, on the 7th of Adar. Moshe then goes to talk to Pharoah when he is 79.
(Incidentally, the Seder HaDorot brings many different opinions of when each of the plagues happened, but see the GR"A on Seder Olam, who says that the 12 months the Mishna says Egypt was plagued starts from G-d appearing to Moshe at the burning bush.)
The Exodus from Egypt was a year later, on the 15th of Nissan in the year 2448, when Moshe had recently turned 80.
Moshe then passes away 40 years later on the 7th of Adar, in the year 2488. Moshe was 120 years old and this was the 40th year the Jews were in the Desert.
The question remains: Why would the Passuk say the Moshe was 80, if he was only 79? I'd have to answer, Miktzas Shana K'shana, part of a year can be considered as a whole year (Rashi in Devarim 13:33 uses this logic to calculate how people could have died in the desert before they were 60). Since Moshe had already started his 80th year, the Torah calls him 80.
One possible problem with this. Seder HaDorot tells us that Aharon was 3 years older than Moshe, and born in 2365, based on the passuk quoted in the question. If Moshe was 79 when he visited Pharoah, would we have to say that Aharon was really 82, in his 83rd year? I guess this would depend on which day Aharon was born, which I did not see written in the Seder HaDorot.
The Kehot Interpolated Chumash says explicitly (bold is chumash text, regular is interpolated commentary):
7 Moses was ten months short of 80 years old and Aaron was 83 years old when they spoke to Pharaoh in the year 2447.
However, the source the are quoting from (Likutei Sichot vol 20, p. 26, note 15) doesn't actually say 10 months, it says "less than 79 and a half". The Lubavitcher Rebbe is using our verse (Shemot 7:7) to prove that someone can be called a certain age, once they have entered that year. In our case, Moshe was called 80 even though he had only entered his 80th year, but was still 79.
It appears that the Kehot Chumash says 10 months because the Lubavitcher Rebbe (in Likutei Sichot vol 6, p. 59, note 18) says that according to the simple understanding of Rashi (Shemot 7:25), as well as the Midrashim that Rashi was based on, there were 3 weeks of warnings before every plague (except Makat Bechorot), even the ones where no warning was mentioned. The Kehot Chumash on verse 7:25 says:
Each plague lasted a month: Moses and Aaron spent three quarters of the month informing Pharaoh about what was going to happen and warning him of the consequences of his obstinacy, and the plague itself lasted a week. Thus, the ten plagues spanned a time-period of ten months.
The Da'as Zkeinim (and the Chizkuni) at the beginning of Parshas Noach addresses this issue in a different context - The posuk says תמים by Noach, and the Midrash says (Bereishis Rabba 30:8) that anyone described as such lived to an age the which is the multiple of 7 (full שבוע). Noach's 950 do not add (or divide) up. He answers that he lived this amount from the time which the Torah described him as תמים, the 350 years after the Mabul. However, there is an extra year, the year of the Mabul itself, which came after he was described as תמים! Says the Da'as Zkeinim:
סלק שנת המבול שאינה נחשבת לפי שנשתנו בה סדרי בראשית
Remove the year of the Mabul, which is not counted because the order of Creation was altered
So a year in which the laws of nature are suspended does not count.
This answers a very similar question to your own:
the Torah says that Noach was 600 at the start of the flood (Bereishis 7:6), and that he lived 350 years after the flood (Bereishis 9:28), and that he lived a total of 950 years (Bereishis 9:29). So what happened to the year of the flood? It isn't counted, as above.
Similarly by the age of Moshe, the year of the Makkos was not counted as a year of his life, as it was a year in which the laws of nature were not firmly in place (I can't find the medrash which says this explicitly, but I have a team of scholars working on it). Thus, Moshe was still 80 for the count of his years when they left Egypt, and there were 40 years in the desert before he died at 120.
It is possible that when the Chumash says Moshe was 80 that it either is rounding (79 rounded up to 80) or that it does not mean right then, but that at some point in the year long process of speaking to Pharaoh, Moses was 80 (that potion being the final 5 weeks in Egypt, when admittedly, Moses really wasn't speaking to Pharaoh).
Exodus Chapter 7 / Pasuk 7
.ז וּמֹשֶׁה, בֶּן-שְׁמֹנִים שָׁנָה, וְאַהֲרֹן, בֶּן-שָׁלֹשׁ וּשְׁמֹנִים שָׁנָה--בְּדַבְּרָם, אֶל-פַּרְעֹה
- And Moses was 80 years old, and Aaron 83 years old, when they spoke unto Pharaoh. It seems from the language of the Pasuk 7 that he turned 80 only after he and Aron both spoke to Pharaoh together.
There are only 2 time when it actually says that Moshe and Aaron spoke to Pharaoh together, as Pasuk 7 describes. The first encounter is all the way in the beginning.
Exodus Chapter 5/ Pasuk 1
א וְאַחַר, בָּאוּ מֹשֶׁה וְאַהֲרֹן, וַיֹּאמְרוּ, אֶל-פַּרְעֹה: כֹּה-אָמַר יְהוָה, אֱלֹהֵי יִשְׂרָאֵל, שַׁלַּח אֶת-עַמִּי, וְיָחֹגּוּ לִי בַּמִּדְבָּר.
And afterward Moses and Aaron came, and said unto Pharaoh:'Thus saith the LORD, the God of Israel: Let My people go, that they may hold a feast unto Me in the wilderness.
Second encounter took place during the 7th Plague of the locusts.
Exodus Chapter 10 / Pasuk 3-4
ג וַיָּבֹא מֹשֶׁה וְאַהֲרֹן, אֶל-פַּרְעֹה, וַיֹּאמְרוּ אֵלָיו כֹּה-אָמַר יְהוָה אֱלֹהֵי הָעִבְרִים, עַד-מָתַי מֵאַנְתָּ לֵעָנֹת מִפָּנָי; שַׁלַּח עַמִּי, וְיַעַבְדֻנִי
And Moses and Aaron went in unto Pharaoh, and said unto him:'Thus saith the LORD, the God of the Hebrews: How long wilt thou refuse to humble thyself before Me? let My people go, that they may serve Me.
ד כִּי אִם-מָאֵן אַתָּה, לְשַׁלֵּחַ אֶת-עַמִּי--הִנְנִי מֵבִיא מָחָר אַרְבֶּה, בִּגְבֻלֶךָ.
Else, if thou refuse to let My people go, behold, to-morrow will I bring locusts into thy border;
However you need to go back and read Pisukim 1 thru 6 / Charter 7, before you can understand what Pasuk 7 is saying, because it's one long statement/commanded. We see only here is there an actual commanded for both Moshe and Aron to speak to Pharaoh. And only after Hashem commanded them together did he Moshe turn 80. And this takes place after Moshe first returns from Pharaoh and his second encounter with Hashem.
א וַיֹּאמֶר יְהוָה אֶל-מֹשֶׁה, רְאֵה נְתַתִּיךָ אֱלֹהִים לְפַרְעֹה; וְאַהֲרֹן אָחִיךָ, יִהְיֶה נְבִיאֶךָ. ב אַתָּה תְדַבֵּר, אֵת כָּל-אֲשֶׁר אֲצַוֶּךָּ; וְאַהֲרֹן אָחִיךָ יְדַבֵּר אֶל-פַּרְעֹה, וְשִׁלַּח אֶת-בְּנֵי-יִשְׂרָאֵל מֵאַרְצוֹ. ג וַאֲנִי אַקְשֶׁה, אֶת-לֵב פַּרְעֹה; וְהִרְבֵּיתִי אֶת-אֹתֹתַי וְאֶת-מוֹפְתַי, בְּאֶרֶץ מִצְרָיִם. ד וְלֹא-יִשְׁמַע אֲלֵכֶם פַּרְעֹה, וְנָתַתִּי אֶת-יָדִי בְּמִצְרָיִם; וְהוֹצֵאתִי אֶת-צִבְאֹתַי אֶת-עַמִּי בְנֵי-יִשְׂרָאֵל, מֵאֶרֶץ מִצְרַיִם, בִּשְׁפָטִים, גְּדֹלִים. ה וְיָדְעוּ מִצְרַיִם כִּי-אֲנִי יְהוָה, בִּנְטֹתִי אֶת-יָדִי עַל-מִצְרָיִם; וְהוֹצֵאתִי אֶת-בְּנֵי-יִשְׂרָאֵל, מִתּוֹכָם.
ו וַיַּעַשׂ מֹשֶׁה, וְאַהֲרֹן--כַּאֲשֶׁר צִוָּה יְהוָה אֹתָם, כֵּן עָשׂוּ.
6 And Moses and Aaron did so; as the LORD commanded them, so did they.
ז וּמֹשֶׁה, בֶּן-שְׁמֹנִים שָׁנָה, וְאַהֲרֹן, בֶּן-שָׁלֹשׁ וּשְׁמֹנִים שָׁנָה--בְּדַבְּרָם, אֶל-פַּרְעֹה.
7 And Moses was 80 years old, and Aaron 83 years old, when they spoke unto Pharaoh.
So only after Hashem commanded them together (Exodus Chapter 7 / Pasuk 1 thru 7 to speak to pharaoh, which takes place by the 7 Plague did Moshe turn 80 on the 7th of Adar... 1 month and 7 days before they left Egypt.
The first encounter in Charter 5 Pasuk 1 Aaron was not Commanded by Hashem to speak to Pharaoh, only Moshe was. So that first encounter does not count. Charter 4 / Pasuk 13 thru 27
יג וַיֹּאמֶר, בִּי אֲדֹנָי; שְׁלַח-נָא, בְּיַד-תִּשְׁלָח
יד וַיִּחַר-אַף יְהוָה בְּמֹשֶׁה, וַיֹּאמֶר הֲלֹא אַהֲרֹן אָחִיךָ הַלֵּוִי--יָדַעְתִּי, כִּי-דַבֵּר יְדַבֵּר הוּא; וְגַם הִנֵּה-הוּא יֹצֵא לִקְרָאתֶךָ, וְרָאֲךָ וְשָׂמַח בְּלִבּוֹ
כז וַיֹּאמֶר יְהוָה אֶל-אַהֲרֹן, לֵךְ לִקְרַאת מֹשֶׁה הַמִּדְבָּרָה; וַיֵּלֶךְ, וַיִּפְגְּשֵׁהוּ בְּהַר הָאֱלֹהִים--וַיִּשַּׁק-לוֹ.
- And the LORD said to Aaron: 'Go into the wilderness to meet Moses. 'And he went, and met him in the mountain of God, and kissed him.