We must -> We have to
These are both in common usage still - as a native speaker I would use "must" for emphasis, or to talk about things we should consider doing rather than absolutely are required to do. For example
"We must get around to getting you that new dress..."
In this context "have to" wouldn't work.
Incidentally note the difference between two pronunciations of
"a list of things we have to do in our holidays"
pronounced [hafta] it is obligation, pronounced [havtu] it is a matter of possibility (What things do we have to do at Easter camp? We can go fishing, sailing, rock climbing, ...)
Another related one
"she was supposed to have killed him"
where the voicing on supposed makes the "thought" meaning and the devoicing the modal meaning. The dropping of segments including voicing and differences in place of articulation (gotta, haft, sposta) is part of the entropic pressure on language, and it is those things that are becoming common frequent idioms that are most affected. It is the same process that lead to "the day" -> "to day" -> "to-day" -> "today" and "the morrow"... (note cognate Morgen in German still means both morning and tomorrow: in the morning = tomorrow).
Also I see the same affect in "one of" -> "one off" and "would have" -> "would've" -> "would of" -> "wouldf".
May I come in? -> Do you mind if I come in?
Actually I am not that polite or pedantic, and would say "Can I come in?" [knai kmin].
All are quite reasonable, your two are both polite, but my version is the most natural.
We don't have to leave yet. -> We don't gotta go yet.
I wouldn't say either, but would certainly use "have to" or "need to" rather than "don't gotta". I would also say "I've got to go now" or "I have to go now" with almost equal likelihood, the former more informal but I could still say either in an important meeting or phone call (and have), as well as "I really must go now".
In terms of what is going on here, in every community, in every new generation, language is changing and new idioms are emerging (like the many uses of "like"). But the international media, and in particular movies and TV shows, means this spreads and we no longer have the insular effects to the same degree.
In practice, it is important to learn the new modals "hafta", "gotta", "sposta", "kinda", "like" if you want to fit in and sound natural/native. The last two though I wouldn't use in a formal context.