How to order get_categories() in the same order as the menu?

There is no header-menu.php, that bit of code is creating a WP Menu, have a look at this.

You could create another menu for the footer. Or if you need more control of the markup, you could use your category code, which uses get_categories() and then sort them how you like. More info on get_categories().

Here is an example of sorting by name.

$categories = get_categories( array(
    'orderby' => 'name',
    'order'   => 'ASC'
) );

So your the entire code block would look like this.

$categories = get_categories( array(
    'orderby' => 'name',
    'order'   => 'ASC'
) );

foreach($categories as $category) {
  echo '<a href="' . get_category_link($category->term_id) . '">' . $category->name . '</a>';
}

Edit (Copy Main Navigation in Footer): You can copy your main navigation to the footer by adding this code in your footer.php.

<nav class="footer-navigation">
    <?php
        wp_nav_menu( array(
        'theme_location' => 'header-menu',
        'fallback_cb' => 'false',
        ) );
    ?>
</nav>

Edit 2 (Array of Nav Items):

You can build your own array using wp_get_nav_menu_items(). Docs here
and Examples here