Você pode usar xorriso . Não me lembro por que, mas acho que isso não é possível com o mkisofs.
Tente:
xorriso -as mkisofs \
-isohybrid-mbr /usr/lib/syslinux/mbr/isohdpfx.bin \
-c isolinux/boot.cat \
-b isolinux/isolinux.bin \
-no-emul-boot \
-boot-load-size 4 \
-boot-info-table \
-eltorito-alt-boot \
-e boot/grub/efi.img \
-no-emul-boot \
-isohybrid-gpt-basdat \
-o /path/to/tmp.iso \
/path/to/tmp
Isso produzirá uma iso MBR / EFI híbrida