That's a LOT of healing, you shouldn't have a problem surviving the burst from the mage. If its a normal freeze mage, without giants, you shouldn't have too much of a trouble, there is absolutely no way then can burn through 30+30 health, even with Alexstrasza. Against giants you should be fine too as long as you have equality and/or peacekeepers.
Try to play as many minions as you can to force him to start using freezes as early as possible (make sure to leave some in hand in case of flamestrike, this means using tokens on every turn; if he fireblasts them every time that's 2 mana less for him to use). Your board should survive the freezes as long as you have answers to the doomsayer. My favorite is Stampeding Kodo - an amazing card to have in your deck, especially due to its synergy with peacekeeper. I'll always keep it in the starting hand against a mage (don't mulligan for it as having enough minions to actually force the doomsayer is more important). Equality can backfire really hard, better save it for Antonidas in case you're unable to clear him otherwise.
I have a harder time with priests than any other class. It is a very delicate balance and hoping they don't steal your best cards with their thieving ways. I haven't been playing long enough to know if they are just the class that Paladin doesn't match up well against. It feels as though it always comes down to can they pull off a huge health taunt once I've already cleared the board twice. What is your strategy when playing a thief? Oh, I mean priest. ;)
Assuming both are playing control, Priests are a fairly good matchup since they are very reactionary and you don't make any big plays early on, whereas late game they run out of answers very quickly. Focus on maintaining the board presence to force them to use their cards, you won't be able to damage them much anyway. GoK's are scary and you can hope to bait out SW:D with them, which allows you to pull out your big guns, though be prepared to deal with your own minion in case they do run Mind Control (which is why you want to delay playing your big legendaries as much as possible, hoping that they will waste MC on a GoK or something). Tirion/Ysera are huge keys to our lategame. They will probably find ways to kill Tirion himself, but its the sword you're most interested in. Ysera is game over for them if they don't run MC or alchemists since there is absolutely no way they can kill it.
If you can fit in a Cairne or Rag its can also be a very tempting card to MC and those are a lot easier to deal with.
Thoughtsteal is bad if they are very lucky to draw your legendaries, but the chance is small enough to not worry about it too much. If it happens, well, tough luck, even the best matchups can lose to bad draws.