He had his great footwork before he started training TKD under, I think it was Jhoon Ree. Anyway, he learnt that balance from great legs lended a lot of power to your punches. Also, coming from personal experiences, the torquing of your hips used much in TKD can be used with great effect in boxing for hooks and crosses, maybe something Ali picked up, but I'm not sure. It's just all speculations.
I got two fists.. Don't make me use my head as well!