theme_links() override has no effect
You can override the menu wrapper in this manner:

function YOURTHEME_menu_tree__MENU_NAME($variables) {
  return '&lt;nav class="menu'.$variables['delta'].'"&gt;' . $variables['tree'] . '&lt;/nav&gt;';
}