template.php

<?php

/**
 * This snippet adds extra classes to Drupal
 * menu leafs (li tags) and menu itself (ul tags).
 */

/**
 * Since the standard preprocess function for menu tree, which is
 * template_preprocess_menu_tree, located in includes/menu.inc,
 * tends to overwrite all information about menu being rendering,
 * contained in $variables['tree'], with this bit of code:
 *
 * $variables['tree'] = $variables['tree']['#children'],
 *
 * we need to override this preprocess function with our own.
 */

/**
* Implements HOOK_theme().
*/
function MYTHEME_theme(&$existing, $type, $theme, $path) {
  $mytheme['menu_tree'] = $existing['menu_tree'];
 
  // Here's the overriding declaration
  $mytheme['menu_tree']['override preprocess functions'] = TRUE;

  array_unshift($mytheme['menu_tree']['preprocess functions'], 'MYTHEME_preprocess_menu_tree_override');
  
  return $mytheme;
} 
 
function MYTHEME_preprocess_menu_link(&$variables) {
 $element = &$variables['element'];
 
 $element['#attributes']['class'][] = 'leaf-lvl-'.$element['#original_link']['depth'];
 
 if(in_array('active', $element['#attributes']['class'])) {
   $element['#attributes']['class'][] = 'leaf-lvl-'.$element['#original_link']['depth'].'-active';
 }
 
 if(in_array('expanded', $element['#attributes']['class'])) {
   $element['#attributes']['class'][] = 'leaf-lvl-'.$element['#original_link']['depth'].'-expanded';
 }
 
 if(in_array('active-trail', $element['#attributes']['class'])) {
   $element['#attributes']['class'][] = 'leaf-lvl-'.$element['#original_link']['depth'].'-active-trail';
 }
 
 if ($element['#below']) {
   $element['#below']['#depth'] = $element['#original_link']['depth'] + 1;
 }
}

function MYTHEME_preprocess_menu_tree_override(&$variables) {
 $variables['tree_raw'] = $variables['tree'];
}

/**
* Add level classes to the menu tree.
*
* @param $variables
*   An array of variables to pass to the theme template.
*/
function MYTHEME_menu_tree(&$variables) {
  $menu_level = isset($variables['tree_raw']['#depth']) ? $variables['tree_raw']['#depth'] : 1;
  $class = "menu menu-lvl-".$menu_level;
  return '<ul class="'.$class.'">' . $variables['tree'] . '</ul>';
}
 

Does this code work for you? I'm getting "menu menu-lvl-1" for every UL in the menu.

You need to replace MYTHEME_preprocess_menu_tree_override with your theme, same was happening for me