It's actually fairly easy to have Mulroney lose, given the fact that for most of the campaign, the PCs were in trouble. Interestingly, there is a fairly decent chance that, given better campaigns, any of the following four options could happen:
a) Liberals win a majority
I'd say this is the most likely of the first three scenarios. Here, the Liberals, not the PCs, would suffer the brunt from the economic downturn of the early 1990s and the almost certainly difficult attempts to amend the constitution (which I believe is likely to be attempted regardless of who's in power). In 1992 or 1993, when the government would head to the polls, I think the PCs would win a fairly decent majority against Turner's Liberals. I don't imagine the Bloc Quebecois, or a similar party, would be formed or have as much success, as I imagine Quebecers would likely stick with the PCs. Similarly, I doubt Reform would do all that well, as without the PCs in power Westerners wouldn't blame them for their feeling of alienation.
Depending on whether or not the NDP comes to power in Ontario and/or British Columbia (which may or may not happen given the butterflies), there's a chance that they might be able to form the official opposition. Either way, though, I don't see the Liberals doing as poorly as the PCs did in 1993.
b) The NDP wins a majority
Less likely, but still possible, as Broadbent was very popular. Like the above scenario, given the economy and constitutional problems, I imagine they would be defeated in 1992/93, likely falling to third. Between the PCs and the Liberals, I suspect that the Liberals would be more likely to win, though I imagine it would be close. Like the above scenario, I struggle to see the Bloc or Reform getting off the ground.
c) PCs win a minority, leading to a Liberal-NDP coalition
A more interesting scenario that I don't think is discussed as often, with the Liberals and NDP forming an anti-Free Trade coalition after the election. The government would probably last around 2 or 3 years, similar to the earlier Liberal-NDP accord in Ontario and the later Liberal-NDP coalition plan in 2008, so an election would probably be held in 1990 or 1991. It's hard to say who would win that election: IOTL the economy was better than it was in 1993, but there were still signs of a slump, and it's hard to say how the constitutional issue would have proceeded with both the Liberals and NDP in charge.
d) Liberals or NDP win a minority
Hard to say how this proceeds. Likely wouldn't last all that long, but the timing of the election is key. If it's held in 1990 or 1991, whoever wins will likely be blamed for the poor economy and lose re-election (like Bob Rae in 1995 IOTL).