The short answer to "Why the two meanings of circumcision and word are associated with milah?", is because the Torah associates these ideas of circumcision and word and says that they are connected.
As is pointed out in the question, the Hebrew word מילה, can mean either word, like is used in Chullin 139b.
א"ר אשי אמר לי [ר'] חנינא מילין מילין ס"ד אלא אימא במילין:
or circumcision, like is used in Shabbat 130a.
כלל אמר רבי עקיבא כל מלאכה שאפשר לעשותה מערב שבת אינה דוחה את השבת (ומילה) שאי אפשר לעשותה מערב שבת דוחה את השבת:
The reason for this association is because both of these usages are a reference (Remez) to the concept of covenant (ברית), as in the Covenant between the Halves (ברית בין הבתרים) found in Bereshit 15:4-15.
This is because, as is stated in Reishit Chochmah, Sha'ar HaKedushah, Chap. 17, Milah (מילה) is the Seal of the King (חותמא דמלכא). The letters (מיל"ה) are Roshei Teivot for "מי יעלה לנו השמימה" (Who will ascend to Heaven for us?) found in Devarim 30:12. And the seal of G-d's name is from the final letters of the phrase (a Notarikon), which form G-d's name (יהו"ה). That to approach G-d in Heaven, like Moshe Rabbeinu when he ascended to receive the Torah requires one to be circumcised (Moshe Rabbeinu, like Noach, was born circumcised.). This concept of the Seal of the King also follows the commentary of Chomat Anak to this posuk in Devarim.
The brit (as in Brit Milah) is the sign (or seal) of the covenant (זאת אות הברית), which is also an allusion to Noach, the flood, which like circumcision, removed the blemish from the world via the upper waters (rain), the intermediate waters (tidal and storm surge) and the lower waters (geysers and liquefaction from earthquakes), and G-d's sign (the rainbow, הקשת) recalling all of that (see Bereshit, parshat Noach, 9:12 and 9:17).
There is an upper level of this covenant (an intermediate level of this covenant which is not associated with your question) and a lower level, below. (ראש תוך וסוף) as in Roshei Teivot, Tochei Teivot and Sofei Teivot. And this corresponds to what is called the three pillars, or columns (Kav HaYamin/Right, Kav HaSm'ole/Left and Kav HaEmtzo'ee/Center) discussed in kabbalah which begin in intellect with Chochmah/Wisdom, Binah/Understanding and Da'at/Applied Knowledge (the union of abstract knowledge with material, physical existence) and evolve into the Middot which begin with Chesed, Gevurah and Tiferet and which correspond to the three Avot, Avraham, Yitzchok and Yaacov. In masculine form, there are three qualities of intellect, six emotional qualities and the union with the material/physical called Malchut/Kingship for a total of ten. But in the feminine form there is a discrete fourth level which transcends intellect called Keter/Crown. Keter and Malchut are like opposite sides of the same coin. Keter is above and Malchut is below.
The lower level of the seal is the place of the circumcision, the covenant of Avraham (מילה), also called the Covenant of the Sexual Organ (ברית המעור) as is found in Sefer Kehilat Yaacov, Brit HaMa'or. To either side of the Milah are the ten toes of the feet, five to the right and five to the left.
Below, meaning the male reproductive organ, that which joins husband and wife to be one, a physical, material manifestation of the conclusion of the first sentence of the Shema, HaShem is one as is stated in Reishit Chochmah, Sha'ar HaKedushah, Chap. 16, beginning (וכד מתחברין דכר ונוקבא כדין איתעבידו חד כו")
(It should be noted that it is the custom of many to learn these sections of Sha'ar HaKedushah in preparation for marriage.)
The upper level, which parallels the Milah, is the place of the tongue (in ones mouth). This is called Covenant of the Tongue, as is mentioned in Sefer Kehilat Yaacov, Brit Lashon (ברית לשון). And so too here, to the left and right of the tongue are the ten fingers of the hands.
Here too we manifest G-d’s unity through speaking the words of His Torah and not profaning His name through speaking Lashon HaRah.
And this association of the Brit Milah and the Brit Lashon is emphasized in Reishit Chochmah, Sha'ar HaKedushah, Chap. 17 beginning with the words:
> גם סבת הקרי עצמותו ועיקרו כו"
and continuing:
> והטעם שכבר פירשנו שהדיבור הוא רוחני דומה לזרע הגשמי כו"
This connection is also discussed and emphasized by Rabbi Meir Paprosh HaKohen in Sefer Ma'orei Ohr, Letter Beit, Chap. 40 (ברית), Rabbi Moshe Cordevero in his Sefer Pardes Rimonim, Sha'ar 23, Sha'ar Archei HaKinuyim, Chap. 2, Brit (ברית). And is also discussed by Rabbi Yosef Gikatilla, the student of Rabbi Avraham Abulafia, in his sefer, Sha'arei Ohrah, HaSha'ar HaSheni, Sefirat HaYesod, beginning with the words:
> ולפעמים נקראת מדת אל ח"י בתורה ברית כו""