The source in the Torah that you quote from is Devarim 6:13. This is as it is brought by Rambam in his Sefer HaMitzvot, Positive Mitzvot, 5. The Mishnah that Rambam is referring to is the Baraita of the 32 Middot of Aggadah. Like is stated in the Otzar Midrashim
הרמב״ם בספר המצות (עשין ל״ז) מביא מדה י״ז בנוסחא אחרת, ושם (עשין ה׳) מביא בשם משנתו של ר״א בנו של ריה״ג מנין לעיקר תפלה מצוה מהכא את ה׳ אלהיך תירא ואותו תעבוד, ואין זה בנוסחא לפנינו, גם הרשב״ץ מביא ממנו מה שאינו לפנינו בברייתא, ומזה ראיה כי היה לפניהם נוסח אחר
the specific version of text used by Rambam is not the same version of the text we have today. So to understand how Rambam understands this statement requires looking at his Mishnah Torah, Hilchot Tefillah, 1:1.
מצות עשה להתפלל בכל יום שנאמר ועבדתם את ה' אלהיכם, מפי השמועה למדו שעבודה זו היא תפלה שנאמר ולעבדו בכל לבבכם אמרו חכמים אי זו היא עבודה שבלב זו תפלה
The Rambam's statement "מפי השמועה למדו שעבודה זו היא תפלה" means according to Yad Malachi that this is the meaning of the word as taught, teacher to student, generation after generation, directly from Moshe Rabbeinu and that this meaning has an allusion, meaning a type of metaphor, parable or other indirect reference to it in the written portion of the Torah (אסמכתא בקרא).
A person who argues that it doesn't mean this and tries to argue that it means something else is essentially disagreeing with the teaching of Moshe Rabbeinu in a fashion similar to Korach and his group.
The Targum Onkelos translates this expression like Moshe Rabbeinu saying and serve Him (ואתו תעבד) means and worship Him (וקדמוהי תפלח), the idea of prayer.
Like is known from Hoshea 14:3, prayer took the place of the service in the Temple after the destruction of the Temple. This follows what we say in the Tachanun each morning after reciting Korbanot.
This source posuk from Devarim lists three different activities. The first listed is commonly translated, like you do, as fearing the L-rd, your G-d (from the verb תירא).
But another way to understand this expression is like is taught by Rabbi Eliyahu De Vidas in the introduction to Sefer Reishit Chochmah. He explains that the idea of fearing G-d is about action.
This is as it is understood from the use of the word in Tehillim 76:9. משמים השמעת דין ארץ יראה ושקטה
From the Heavens judgement is heard, the earth shakes (quakes) and is silent.
David HaMelech is referring in this Psalm to the teaching found in tractate Shabbat 88a which explains that when the nation of Israel hesitated in accepting the oral Torah, this caused an earthquake. After they agreed to accept the oral Torah, the quaking stopped.
In this context, the verb which is commonly translated as fear is meant here to emphasize the expression of fear, meaning shaking and movement. It is the idea of action, meaning the performance of the mitzvot of action, like wearing tzitzit and tefillin or shaking the lulav.
And so the posuk you source from Devarim means that we were brought out of Mitzrayim in order to fulfill the mitzvot of action and to worship G-d through prayer.
And through this we accomplish the third element of the posuk which is establishing G-d's name (like Onkelos translates "tishavea" as ובשמיה תקים) like it says at the end of Aleinu, On this day, He will be one and His name will be one.