How to prevent Widget from echoing to wrong position in DOM

dynamic_sidebar will output the sidebar when it is called. Try using it with buffering and store into a variable as below:

<ul class="menu">
    <?php
        $locations = get_nav_menu_locations();
        if ( isset( $locations[ 'mega_menu' ] ) ) {
            $menu = get_term( $locations[ 'mega_menu' ], 'nav_menu' );
            if ( $items = wp_get_nav_menu_items( $menu->name ) ) {
                foreach ( $items as $item ) {
                    echo "<li>";
                    echo "<a href=\"{$item->url}\">{$item->title}</a>";
                    ob_start();
                    dynamic_sidebar('mega-menu-widget-area-' . $item->ID);
                    $sidebar = ob_get_contents();
                    ob_end_clean();
                    if ( is_active_sidebar( 'mega-menu-widget-area-' . $item->ID ) ) {
                        echo "<div id=\"mega-menu-{$item->ID}\" class=\"mega-menu\">";
                            echo $sidebar;
                        echo "</div>";
                    }
                echo "</li>";
                }
            }
        }
    ?>
</ul>

Hope this helps!!