Вот один из способов:

function level(parent, element, tagName) {
    return (!element.parentNode || element.parentNode === parent) ? 0 :
      (element.tagName === tagName ? 1 : 0) + level(parent, element.parentNode, tagName);
}

const menuParent = document.querySelector('div.nav-menu');

menuParent.querySelectorAll('div').forEach(div => {
    div.setAttribute("data-level", level(menuParent, div, "DIV"));
});

Я предлагаю вам свернуть свою собственную версию; это не вершина элегантности (но она лаконична).

Дайджест версия читателя

Я переписал это в более доступную версию. Надеюсь, это поможет вам двигаться вперед!

/* Note that this is a recursive function */
function level(parent, element, tagName) {

  /* We are at top level element, return 0 */
  if (!element.parentNode) {
    return 0;
  }

  /* We have reaced the predestined parent, return 0 */
  if (element.parentNode === parent) {
    return 0;
  }

  /* If this element matches the tag name, return 1 + results for all the parents */
  if (element.tagName === tagName) {
    return 1 + level(parent, element.parentNode, tagName);
  }

  /* Otherwise, just return results for all the parents */
  return level(parent, element.parentNode, tagName);
}

/* Find the root element for the menu tree */
const menuParent = document.querySelector('div.nav-menu');

/* Enumerate every <div> under the root element (at *every* level) */
const eachDivUnderParent = menuParent.querySelectorAll('div');

/* Iterate each <div> under <div class="nav-menu"> */
eachDivUnderParent.forEach(divElement => {
  /* Calculate the level at that element */
  const divLevel = level(menuParent, divElement, "DIV");
  /* Set the calculated value as `data-level` attribute */
  divElement.setAttribute("data-level", divLevel);
});