The first thing to say about hoochie-coochie, is that it comes in more variations of spelling that I can think of for any expression. Here are some of the possible permutations, all of which can be found in print:
The ‘oo’ can also be ‘ou’
There can be a ‘t’ before the ‘ch’
The ‘ie’ can also be ‘y’ or ‘ee’
The second word might start with a ‘k’
So, depending on your preference, you might spell ‘hoochie-coochie’ as ‘hoochy-coochy’, ‘hootchee-cootchee’, houchy-kouchy’ and so on.
The OED lists twenty different spellings and opts for ‘hootchy-kootchy’ as that was the early name of the dance. I’ve gone for ‘hoochie-coochie’ as that is the most commonly used now.
It’s quite possible, but at this distance in time difficult to verify, that the name ‘hoochie-coochie’ is a variant of the earlier dance the Hokey Cokey. However, it’s more likely that it came from the ‘couchee-vouchee’, which is a similar dance dating from the late 19th century. That’s mentioned in the New York Tribune, September, 1894:
Come, gents, walk right up and see the ‘Couchee-Couchee Dance.’
The first mention of ‘hoochie-coochie’ with any of the many meanings and spellings I can find is in the Arkansas newspaper The Eufaula Daily Times, July 1972:
The “cream and sugar,” “lovey dovey,” “hootchy kootchy” attitude.
The first reference to the expression as the name of a dance is from The St. Paul Daily News, October 1893:
She has traveled… throughout Europe, and while there conceived a number of novel dances; one in particular, which has created considerable comment, she calls the ‘Hootchy Cootchy’.
‘Hootchie-coochie’ has continued to be used widely, more often these days as a suggestive reference to sexual activity rather than to dance.
Many people know the term as the title of Willie Dixon blues classic ‘Hoochie Coochie Man’ recorded by Muddy Waters in 1954.
See other reduplicated phrases.