I couldn't find many references to the specific act of stoning, since I think most would think of this as using a popular phrase. But I agree with the premise of your question, that the Torah doesn't write stuff for no reason, so it would be interesting to learn why Moses picked stoning specifically. This is a suggestion for a partial answer.
Sanhedrin 7b:
אמר ריש לקיש כל המעמיד דיין (על הציבור) שאינו הגון כאילו נוטע אשירה בישראל
Translation: Resh Lakish said: He who appoints an incompetent judge over the Community is as though he had planted an Asherah in Israel.
The Maharal explains this concept in Chidushei Agadot:
כי הדיין נקרא אלקים בכל הכתוב, מפני כי המשפט לאלקים, ולכך זה שהוא דיין ראוי שיהיה נקרא אלקים. ואמרו כל הדן דין אמת לאמתו כאלו נעשה שותף להקב"ה במעשה בראשית, כמו שבארנו בפ"ק דשבת (י' א'). ולכך דיין שאינו הגון נקרא אשירה, כי האשירה היא אל זר וכיון [ש]הדיין נקרא אלקים, וכאשר אינו הגון הוא אל זר, ולכך אמר כאלו נטע אשירה
(In short, one who judges others is doing Hashem's work, so when he is incompetent, he is like a "false god", and whoever appoints such a judge is appointing a "false god".)
So any leader, who appoints himself as leader, and who is incompetent, is as one who "planted an Asherah", and the punishment of basic avoda zara is death by stoning.
We encounter many places, during the travels in the desert, where Bnei Yisrael complain and even blame Moses for their troubles (why did you bring us here, etc.). Here too, Bnei Yisrael might be blaming Moses as an incompetent leader, as a competent one would supply water to his people. If Moses is incompetent, based on the gemara and Maharal above, his punishment would be stoning.
(By the way, Hashem tells Moses then to "pass on before the people", to prove to him that they do not really want to stone him. The midrash even says that Hashem scolds Moses for accusing the people of such thoughts.)
