I don't quite have enough personal experience of enough parts of Mainland China to be able to judge how prevalent it is. I will say however that it is far more prevalent in urban Taiwan (particularly Taipei) than rural Taiwan, and more prevalent across Taiwan than in its closest linguistic areas on the mainland, i.e. Fujian, Zhejiang, Guangdong. I do find more northern Chinese prone to "slurring the sounds", most characteristic of the Beijing dialect of course, but also fairly common in fast speech across the parts of the north that I've been to, from Shandong to the northeastern area.
The 连音 / contraction so common on Taiwan is what you're picking up, enough to be a defining characteristic of casual Taiwan Mandarin, and easily perceived by a Mainland Chinese ear. The "extreme reductions" have been studied by linguistics researchers, and according to this 2009 paper from researchers at University College London, it is actually an ongoing productive process. Vowel + vowel interfaces are most likely to be contracted.
The outcomes of a lot of these contractions are starting to be fossilised, and are changing the phonotactics of colloquial Taiwan Mandarin slightly. Some of these are documented in this 2006 paper from NTU. Certain initials are more resistant to change than others; the labials b-, p-, f-, m- are mentioned as consistently so, with the one exception being 根本 gēnběn which becomes "gèmm" with an elongated m, phonetically [kəmː˥˩].
Of course, removing contrasts do create conflict and confusion. This 2010 paper from UCLA shows that perceptual cues nonetheless remain. Length seems to be increasingly contrastive in this role, as are the exact scale of the tones.
