With speed; fast.
And the Blackfoot who courted each foeman's approach. Faith, `tis hotfoot he'd fly from the stout Father Roach.
N.B. The Blackfoot was an Irish faction, similar to the Terry Alts in the early part of the nineteenth century.
Source: Dictionary of Phrase and Fable, E. Cobham Brewer, 1894
More on Hot-foot from Fact Monster: