My expectation for a mega menu from site owner and user stand point is that it is not purely generated but redacted/currated to show contents that not have to follow the content structure within the site but foremost give a rich overview what the selected navigation topic could provide.
An idea I'm carrying around for a while is to use a mosaic pages to create mega menus. This will allow you to create mega menus with all the freedom to create a "submenu" including static and dynamic content.
A small javascript to load and show that mosaic-submenu-item should be easy to do and one could use an extra p.a.caching rule if there's any performance issue.