Partridge's Dictionary of Slang (5th ed) has the following
entry--
Fuzzy-Wuzzy. A Soudanese tribesman, esp.as a
dervish soldier : commemorated by Kipling in 1890 (reprinted in Barrack-Room
Ballads,1892), as 'a pore benighted 'eathen but a first-class
fighting man'. Military : late C 19-20, obsolescent. Ex his ' 'ayrick 'ead of
'air'. This implies that the term was used, but not invented, by
Kipling.
George Engle