I heard it in the couple movies and podcasts, and was able to trace it to the Cole Porter song "You Do Something to Me" from 1929. I think it's where it came from, but I just want to be sure. Also, how popular it is among native speakers/Americans, and what group of people using it the most? Age, race, gender, type of a person if possible.
It was created by Cole Porter, a songwriter who was known particularly for his exceptionally clever and inventive wordplay. This phrase is just one example.
It is not, however, a commonly used phrase. I find that references to it really are only making allusions to the original source. It isn't in common speech at all. It is and was just a clever line from a lovely song.
The phrase "do that voodoo that you do so well" has been used in two films other than the films that the song has appeared in. Most know it was spoken by Harvey Korman in the movie "Blazing Saddles", but it was also spoken by Col. Sherman Potter in the "MAS*H series, Season 8/Episode 24, "Back Pay", March, 1980, six years after Blazing Saddles was released.
Let's not lose sight of the underlying meaning. When she sings Youdoo voodoo youdoo, she is saying a few things aside from silly wordplay. She is hinting, strongly for the times, that she wants him to do more of the magic that he 'does' to her.
You do something to me = You turn me on.
Something that simply mystifies me = You turn me on.
You have the power to hypnotize me = You turn me on.
Let me live 'neath your spell = You turn me on, and the position suggested is not accidental.
For clarification, listen as Marlene Dietrich sings it.
I know this is an old answer and you probably don't care anymore, but while the expression is not exactly popular, I wouldn't say the expression is totally unused, either. Probably because of the movie Blazing Saddles, I think it is used occasionally by people - and neither ironically nor charmingly, but simply jovially. Google ngrams shows an increased usage starting around 2010, and clicking through shows it being used in several books. In some cases, they are references to the original song, but in other cases not. Here's an example from "Bombshell: A Novel" in 2013:
“Hell, I'll do whatever voodoo that you do, Nona."
It's fiction, but I think that's a pretty accurate example of how somebody might use it. I know I will use it occasionally just as a joking reference, because I know my audience will understand it because of the movie.
The song line has not just one "do" but two: "Do do that voodoo that you do so well." The wordplay is brilliant. First the use of the command "do" followed by the ordinary verb "do," and the rhyme with voodoo. It's one of the cleverest lines in all of songdom, and very very famous; it's so incredibly sad that so many of you didn't seem to know the song and had to research it. Suggest you listen to other Cole Porter songs too ("You're the Top," "Anything Goes," "Let's Do It," "Let's Misbehave," "Live and Let Live" just a few examples) and make them part of your body of knowledge. The reference in Blazing Saddles is simply to the song; it prompts the audience to laugh because presumably they know the song.