Music historian Larry Birnbaum states that the 1955 R&B hit "Hands Off", written by Jay McShann and recorded by him with singer Priscilla Bowman, was the "obvious basis" for "Got My Mojo Working", and the two songs were combined by Elvis Presley.
Larry Birnbaum, Before Elvis: The Prehistory of Rock ‘n Roll, 2013, p. 182.
Cole's recording of the song was released by the legendary Baton label from New York City, and it's totally out of this world. No wonder Waters was knocked out when he heard her perform it live :