The term walk Spanish has been put to many uses, but most of them refer to the method of forcing another person along by grabbing him by the collar or scruff of the neck and the seat of the pants, and propelling him forward on tiptoe; when used this way, the term is synonymous with bum's rush. This sense of the phrase may be the original one, since it is thought to come from the way Spanish pirates encouraged their captives to walk the plank. There is a rough children's game of the same name and style which is also called walk turkey.
Tom Waits is probably using walking Spanish in a different sense, however; the song alludes to a more dignified departure than that executed by Spanish pirates. It can also refer to strutting, walking unsteadily, firing someone from his job, and making a person toe the line or do anything against his will.
Source: George W. Stimpson, Why Do Some Shoes Squeak? and 568 Other Popular Questions Answered (New York: Bell Publishing Co., 1984), 263-3.