2 edit to have $link['language']->language
source | link
    $output .= '<div class="desktop-only">';
    // This will give the native name of the lang like 'Français'
    $output .= l($link['language']->native, $link['href'], $link);
    // This will give the name of the lang like 'French' if the website is in English
    // $output .= l($link['language']->name, $link['href'], $link);
    $output .= '</div>';
    $output .= '<div class="mobile-only">';
    $output .= l($link['title']$link['language']->language, $link['href'], $link);
    $output .= '</div>';
    $output .= '<div class="desktop-only">';
    // This will give the native name of the lang like 'Français'
    $output .= l($link['language']->native, $link['href'], $link);
    // This will give the name of the lang like 'French' if the website is in English
    // $output .= l($link['language']->name, $link['href'], $link);
    $output .= '</div>';
    $output .= '<div class="mobile-only">';
    $output .= l($link['title'], $link['href'], $link);
    $output .= '</div>';
    $output .= '<div class="desktop-only">';
    // This will give the native name of the lang like 'Français'
    $output .= l($link['language']->native, $link['href'], $link);
    // This will give the name of the lang like 'French' if the website is in English
    // $output .= l($link['language']->name, $link['href'], $link);
    $output .= '</div>';
    $output .= '<div class="mobile-only">';
    $output .= l($link['language']->language, $link['href'], $link);
    $output .= '</div>';
1
source | link

You have to copy and paste the entire theme_links function and rename it like you did mytheme_links__locale_block

function theme_links__locale_block($vars) {
  $links = $vars['links'];
  $attributes = $vars['attributes'];
  $heading = $vars['heading'];
  global $language_url;
  $output = '';

  if (count($links) > 0) {
    // Treat the heading first if it is present to prepend it to the
    // list of links.
    if (!empty($heading)) {
      if (is_string($heading)) {
        // Prepare the array that will be used when the passed heading
        // is a string.
        $heading = array(
          'text' => $heading,
          // Set the default level of the heading.
          'level' => 'h2',
        );
      }
      $output .= '<' . $heading['level'];
      if (!empty($heading['class'])) {
        $output .= drupal_attributes(array('class' => $heading['class']));
      }
      $output .= '>' . check_plain($heading['text']) . '</' . $heading['level'] . '>';
    }

    $output .= '<ul' . drupal_attributes($attributes) . '>';

    $num_links = count($links);
    $i = 1;

    foreach ($links as $key => $link) {
      $class = array($key);

      // Add first, last and active classes to the list of links to help out themers.
      if ($i == 1) {
        $class[] = 'first';
      }
      if ($i == $num_links) {
        $class[] = 'last';
      }
      if (isset($link['href']) && ($link['href'] == $_GET['q'] || ($link['href'] == '<front>' && drupal_is_front_page()))
         && (empty($link['language']) || $link['language']->language == $language_url->language)) {
        $class[] = 'active';
      }
      $output .= '<li' . drupal_attributes(array('class' => $class)) . '>';

      if (isset($link['href'])) {
        // Pass in $link as $options, they share the same keys.
        $output .= '<div class="desktop-only">';
        // This will give the native name of the lang like 'Français'
        $output .= l($link['language']->native, $link['href'], $link);
        // This will give the name of the lang like 'French' if the website is in English
        // $output .= l($link['language']->name, $link['href'], $link);
        $output .= '</div>';
        $output .= '<div class="mobile-only">';
        $output .= l($link['title'], $link['href'], $link);
        $output .= '</div>';
      }
      elseif (!empty($link['title'])) {
        // Some links are actually not links, but we wrap these in <span> for adding title and class attributes.
        if (empty($link['html'])) {
          $link['title'] = check_plain($link['title']);
        }
        $span_attributes = '';
        if (isset($link['attributes'])) {
          $span_attributes = drupal_attributes($link['attributes']);
        }
        $output .= '<div class="desktop-only">';
        // This will give the native name of the lang like 'Français'
        $output .= '<span' . $span_attributes . '>' . $link['language']->native . '</span>';
        // This will give the name of the lang like 'French' if the website is in English
        // $output .= '<span' . $span_attributes . '>' . $link['language']->name . '</span>';
        $output .= '</div>';
        $output .= '<div class="mobile-only">';
        $output .= '<span' . $span_attributes . '>' . $link['title'] . '</span>';
        $output .= '</div>';
      }

      $i++;
      $output .= "</li>\n";
    }

    $output .= '</ul>';
  }

  return $output;
}

Inside the code you will find the version for mobile and desktop with class added.

    $output .= '<div class="desktop-only">';
    // This will give the native name of the lang like 'Français'
    $output .= l($link['language']->native, $link['href'], $link);
    // This will give the name of the lang like 'French' if the website is in English
    // $output .= l($link['language']->name, $link['href'], $link);
    $output .= '</div>';
    $output .= '<div class="mobile-only">';
    $output .= l($link['title'], $link['href'], $link);
    $output .= '</div>';

Then you'll have to hide the link (display:none;) in CSS depending on the resolution of you screen (with media queries)