Is it necessary to cache data generated by menu_tree_all_data and menu_tree_output called in preprocess_page
No need to cache menu_tree_all_data() as it is already cached; which leaves menu_tree_output(). This function looks fairly light; but it really depends on how many items are in $main_menu_tree. Note that it's not 100% safe to cache menu_tree_output() the way you're currently using it as it uses menu_get_item(). If you were to use the tab_root_href key as part of the cid then that would probably work. If this code only gets called once (my guess as it's in hook_preprocess_page()) then the static cache will not help. The important questions are how fast is your cache backend, how many items are in $main_menu_tree, and how often does this code get called. Knowing that will tell you what's better.

Questions like this can be answered with some help from microtime(). Example below:

// Get current menu item.
$router_item = menu_get_item();
$menu_name = 'main-menu';
// Get the cache ID.
$cid = 'ctm_mobile_menu:' . $vars['language']-&gt;language . ':' . $router_item['tab_root_href'] . ':' . $menu_name;

// Try core static cache.
$menu_output = &amp;drupal_static('menu_tree', array());
if (!empty($menu_output) &amp;&amp; !empty($menu_output[$menu_name])) {
  $mobile_menu = $menu_output[$menu_name];
}
else {
  // Try cache backend
  if ($cache = cache_get($cid) &amp;&amp; !empty($cache-&gt;data)) {
    $mobile_menu = $cache-&gt;data;
  }
  else {
    // Get the rendered output for the $menu_name variable.
    $mobile_menu = menu_tree($menu_name);
    // Save to the cache bin.
    cache_set($cid, $mobile_menu, 'cache');
  }
}



$time_start = microtime(true);
    // Get the entire main menu tree.
    $main_menu_tree = menu_tree_all_data('main-menu');
    // Add the rendered output to the $mobile_menu variable
    $mobile_menu = menu_tree_output($main_menu_tree);
$time_end = microtime(true);
$time = round($time_end - $time_start, 4);
echo "Did non-cached in $time seconds\n";



$time_start = microtime(true);
    // Get current menu item.
    $router_item = menu_get_item();
    // Get the cache ID.
    $cid = 'ctm_mobile_menu:' . $vars['language']-&gt;language . ':' . $router_item['tab_root_href'];

    // Try cache backend
    if ($cache = cache_get($cid)) {
      $mobile_menu = $cache-&gt;data;
    }
$time_end = microtime(true);
$time = round($time_end - $time_start, 4);
echo "Did cached in $time seconds\n";