You're right, now I'm super confused, maybe it's in one of the other packages? Try building the kernel without it, if you don't get an error that says mkbootimg not found then it's all good. Otherwise I can try reinstalling 16.04 and track down what i did to make it work.
edit: you can also try 'android-tools-fsutils' but I can't verify that it has that file at the moment
as for new lichee I haven't tried it but it might work better (or worse) and i wouldn't even bother with the 4.9 BSP as takiser said