I've got kingsize (as in poster format) maps of Mkuzi, Ithala and Umfolozi (the southern part of what is now the Hluhluwe-Imfolozi Park), published by the then Natal Parks board in 1989. The Hluhluwi map was unfortunately out of stock when I bought the others. Not that it makes any difference, I would not have parted with it anyway.

The road network in the park is very limited, online maps such as
this one should give you a pretty good idea. Not that much has changed in Umfolozi/Imfolozi since 1989, I can see.

Johan.