It’s weird but I used just about all my dust to make a pure pally deck, and I did pretty well. But then I made a crumby little murloc deck and I’m destroying everyone. Do you think it’s because the decks I go up against are different at low ranks, or is it because the murloc deck is mostly commons and rares and I’m getting match up against “fair” opponents? Did I waste all that dust on the pure pally deck, or will I need it once I get higher up?
Maybe, the opponents expect to see Pure Paladin so they have some tech cards against it which are useless against murlocs? Also, murloc pala is more like aggro deck, is not it? Well, you will see after more games and at a higher rank. Maybe you will switch then. Anyway, do not regret crafting something you do not seem to need right now. You never know what will future expansions bring.
I think the general rule is to play what you enjoy playing, although winning is also good 
HSReplay, diamond-legend, last 7 days: the only Murlock Paladin deck has 340 games and a 50.2% win-rate. The most-played Pure Paladin has 26k games, and a 56.9% win rate.
At Bronze-Gold, Murloc does better (quite respectable for a small sample size), but is still behind:
Murloc: 860 games, 58.7% win rate
Pure: 6500 games, 65.9% win rate
The Murloc games are also faster on average, but with those percentages, pure Paladin should still climb faster.
Matchmaking is not supposed to look at your deck, just your record of wins and losses. If you switch to the starter basic Mage deck, that should not influence who your next opponent is.