Replace menu links in Drupal 7 using menu_link & menu_tree hooks

Want to add span elements to menu, change ul id or add classes? Need images in menu or some custom style? You can do that by using menu_link for menu items and menu_tree hook for menus itself. To replace all menus remove __MENUNAME.

// Customize menu li & links
function MYTHEME_menu_link__MENUNAME($variables) 
{
	$element	= $variables['element'];
	$sub_menu	= '';

	if ($element['#below']) {
		$sub_menu = drupal_render($element['#below']);
	}

	// Enable this to use html in title, eg img, span or something else...
	$element['#localized_options']['html'] = true;

	$link = l('<span>' . $element['#title'] . '</span>', $element['#href'], $element['#localized_options']);

	return '<li' . drupal_attributes($element['#attributes']) . '>' . $link . $sub_menu . "</li>\n";
}

// Customize menu ul
function MYTHEME_menu_tree__MENUNAME($variables) 
{
	// Change id of menu ul
	return '<ul id="my-custom-menu-id">' . $variables['tree'] . '</ul>';
}

You can probably use preprocess_menu_link or preprocess_links as well, but this seems to be easiest way. Read more about it here.