Here's a blues song that mentions shoes:

HOODOO BLUES
by Bessie Brown

I'm on the war path now, I'm mean and evil I vow,
Some woman stole my man, to get even I've a plan.

Gonna sprinkle ding 'em dust all around her door
Gonna sprinkle ding 'em dust all around her door
Put a spider in her dumplin', make her crawl all over the floor

Goin' 'neath her window, gonna lay a black cat bone
Goin' 'neath her window, gonna lay a black cat bone
Burn a candle on her picture, she won't let my good man alone.

Got myself some gris-gris, tote it up in a sack
Got myself some gris-gris, tote it up in a sack
Gonna keep on wearin' it till I get my good man back

I was born 'way down in Algiers, I wear conjure in my shoes
Born 'way down in Algiers, I wear conjure in my shoes
Gonna fix that woman, make her sing them hoodoo blues.

http://www.luckymojo.com/blueshoodoobrown.html

Here's a comment from that same website:

"In verse 4, "I wear conjure in my shoes" is a clear-cut reference to one method of deploying charms, powders, or wishing-papers; however, it is important to note that | wearing something in the shoe is done for any number of reasons and need not refer to love-rivalry, as in this song. For instance, i have known women who wear violet leaves in their shoes to draw lovers, street prostitutes who wear a mixture of Money Drawing Powder and Law Stay Away Powder in their shoes to turn tricks without being arrested, and folks who place the name of someone they wish to dominate in their shoe so they can rule and have their way by "stepping on them." The zydeco song "Paper in My Shoe" by Boozoo Chavis refers to this practice as well. "