How hard is it to convert appimages into msi style installers that would unzip the app on some directory, notify the OS it got a new app, add a shortcut and uninstaller program ?

You described this almost verbatim: https://github.com/ivan-hc/AM