"Till death do us part" is taken from a traditional marriage vow that uses an old-fashioned -- some would say archaic -- verb construction having the literal meaning, "until death separates us". (To be precise, it's an instance of the present subjunctive, whose purpose in the wording of the vow is to describe a situation that is hypothetical at the time the wedding ceremony is taking place.)
There are several different formulations of the traditional English marriage vow, but all of them are recited in turn by both parties to the marriage contract. One that is contained in the Anglican Book of Common Prayer includes the following declaration to be uttered by the groom:
I, [name of groom], take thee, [name of bride], to my wedded wife, to have and to hold from this day forward, for better for worse, for richer for poorer, in sickness and in health, to love and to cherish, till death us do part, according to God's holy ordinance; and thereto I plight thee my troth.
You may have noticed that the first version of the Beyoncé lyric you quoted ("Not even death can do us part") switches "us do" to "do us"; this is closer to modern syntax, but does not change the meaning. More to the point of your question is the fact that the songwriter has screwed up the structure of the subjunctive by replacing till with not even and inserting the word can into the formula, seemingly in an attempt to turn it into something more akin to a straightforward declarative sentence.
Whether this is because they didn't understand the way the subjunctive form works, or because they were assuming that the audience wouldn't understand the allusion to the marriage vow unless both 'can' and 'do' had been crammed into the lyric, I cannot be sure; but the fact that the album version of the lyric has been changed to "Not even death could make us part," which corrects the grammatical solecism, makes me suspect that ignorance was chiefly responsible for the first version of that line.
(The Wikipedia page devoted to the song, http://en.wikipedia.org/wiki/Sweet_Dreams_(Beyoncé_song) , credits four songwriters -- Beyoncé Knowles, Jim Jonsin, Rico Love and Wayne Wilkins -- which makes the identity of the person(s) responsible for that particular line anybody's guess.)