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.