The story
Unknown. Attested from the 1890s. Compare kouta kouta dance, a similar belly dance also attested from the 1890s. Possibly influenced by forms such as honky-tonk (from 1880s), hula-hula (from 1820s), or hurdy-gurdy (from 1740s). Later forms coochie, cooch appear to derive from hootchy-kootchy.
Etymology from Wiktionary, CC BY-SA 4.0.