It's Mathias who betrays Walter, not Death. Mathias had a deal of some sort with Walter (Walter mentions at one point "It's just like that knight said" and death is no knight), and what other deal could walter want than immortality?
The way I see it, Mathias made a deal with Walter, so that once he does everything according to his master plan he'll have his eternal servant, Death, forget about him and his soul, thus letting him resurrect once he dies.
Of course Mathias had no plans to keep his promise, since he needed the soul of a powerful vampire. And then there's that whole silly "egg" animation which was more than likely supposed to symbolise the rebirth of Mathias as a vampire.
Anyway I still stand by my decision, Death is the most powerful. Even if Dracula owns him, he only owns his earthly manifestation. Once Drac dies in 1999 I guess he also has a non-planned meeting with mr. bonehead.