Filter 'walker_nav_menu_start_el'
and replace the link text.
Prototype, not tested:
add_filter( 'walker_nav_menu_start_el', 'wpse_56028_title' );
function wpse_56028_title( $item )
{
return preg_replace( '~(<a[^>]*>)([^<]*)</a>~', '$1<span>$2</span></a>', $item);
}