There was a dance called the Todalo. I have been unable to find a description of the dance, but it apparently involved shaking and/or shimmying. Apparently the suggestive nature of the dance led to "todalo" being used as a euphemism for something more explicitly sexual.

But I found some song (or tune) titles:

BALTIMORE TODALO, by Eubie Blake, 1909.

THE DARKEY TODALO: A RAGGEDY RAG, by Joe Jordan, 1910.

TODDLING THE TODALO, by Billy Murray, 1911.

Duke Ellington and his trumpeter James "Bubber" Miley wrote and recorded THE EAST ST LOUIS TOODLE-OO in 1926-27, but the spelling was apparently a printer's error, and should have been "todalo."

Regarding the exact meaning and derivation of "todalo," I've found references to a couple of scholarly articles:

On Toodle-oo, Todalo, and Jenny's Toe by Mark Tucker, in American Music, Vol. 6, No. 1 (Spring, 1988), pp. 88-91.

…which is a reply to Jenny's Toe Revisited: White Responses to Afro-American Shaking Dances by Chadwick Hansen, in American Music, Vol. 5, No. 1 (Spring, 1987), pp. 1-19.