Según entiendo sólo debes ir copiando los valores, pues las claves 'menu' pasa a ser 'label' y '__children' a 'pages', ¿o me equivoco?
El primero arreglo es poco consistente con eso, ¿por qué hay 'menumenu' a veces?
Para generar los sub-arrays simplemente debes usar recursividad, que ya lo haces, así que no entiendo cual es la dificultad, es un ejercicio bastante sencillo.
