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