How significant is rolling resistance?
It's the second most important continuous resisting force on a bike.
When you ride uphill, depending on the slope of the hill, the most important resistance is obviously that hill. But it will be paid back when riding downhill (although then your speed increases so much that increasing air resistance eats away your speed due to being non-linear, so only part of the lost speed will be paid back).
When you start from stoplight, the most important resistance is the inertia of your bike and yourself. However, very soon you will be fully at speed and the inertia is not a concern anymore.
However, when considering resistance that affects you always, there are only two main sources, air resistance and rolling resistance, although it could be argued that hub bearings have friction too (and if you use a dynamo hub it has more drag), but generally the friction is insignificant compared to rolling resistance, and for mathematical modeling can easily be combined with rolling resistance to the same term.
Air resistance is the greater of these two at typical riding speeds, but once you start to be tired and your speed drops, the relative share of air resistance decreases due to dropping speed, and the rolling resistance becomes relatively more important.
The main problem of rolling resistance is that it's there always and it can't be overcome. You can overcome air resistance by riding so slowly that it's almost insignificant, and you can overcome air resistance by riding on the drops if you have a drop bar bike, but rolling resistance is always constant and it isn't feasible to reduce it during riding (but during servicing the bike you can choose what tire to install and what pressure to put on it).
I switched the tires on my bike back in March and ever since then, I've noticed that I've lost about 2 mph on average. I just feel slow and notice that where I could coast further before, I have to start pedaling earlier.
Maybe this could be the case. With Continental GP 5000 32mm (CRR 0.003), my flatland speed at a leisurely 110W power level according to a simulator is 25 km/h, with studded winter tires (CRR 0.008) it's 22.4 km/h. However, this is a bit extreme comparison, since studded tires aren't probably what you switched to. Yet, it's extremely important to select low rolling resistance tires: tires with practically no puncture protection (well you can't sell them without puncture protection so they add a protection layer based on snake oil and call it puncture protection), no rubber tread on the sidewalls, 120TPI casing, very thin rubber tread that's made of extremely high quality rubber so it won't have unacceptable treadwear life despite being very thin and low loss, a reasonable width that's not too thick and not too thin (32mm), ability to pump to very great pressures (you probably want 6bar for 32mm), etc.
I went up from 32 mm tires to 42 mm.
I have never been able to find a reasonable 42mm tire. The good tires max out at 32mm, the wider ones being such that they lack the features needed for low rolling resistance.
I didn't think much of rolling resistance before, but I am convinced that it must be the tires.
Likely yes, but there's another possible source: 42mm tires have more air resistance than 32mm tires. That's actually the reason why everyone used to ride 23mm tires on road bikes. Then disc brakes came and made 32mm tires possible, and people noticed that on varying roads maybe having poor quality, the 32mm tires have lower rolling resistance (even though they theoretically have higher rolling resistance on a drum), and riders accept the bigger air resistance of 32mm tires due to having lower rolling resistance in practice.
Of course, if it's the air resistance of tires, it's still the tires.
With all of that, is rolling resistance that significant?
It's so significant that I never ride on anything except GP5000 32mm, unless the roads have snow, ice of sharp gravel distributed over ice to prevent pedestrian accidents due to slipping on ice (this sharp gravel punctures everything except the best puncture protection). I also pump up my tires every 2 weeks to keep rolling resistance low.
Especially, how is it possible my mountain bike tires, which are wider than my road tires, are faster?
Typically tires having tread are slower on paved roads of good quality, but you may have been riding them on roads of poor quality. It's also possible that you don't use appropriate pressure on either the narrow road bike tires or the wide MTB tires: wider tires roll better at the same pressure but should ideally have less pressure for comfort. Also, I suspect a high quality MTB tire with 120TPI casing and design for MTB racing could outperform a heavy road tire that has been designed for maximum puncture protection and nothing else, despite MTB tire being wider and having a tread. Width and tread are not the only sources of rolling resistance.