Yo uso frecuentemente el Tmpgenc dvd author , y aquí tienes un tutorial para realizar los menús ... no es nada complicado.
Aunque creo que sí que tendrás que volver a recodificar los videos (el propio programa lo hace todo en el último paso), para que queden insertados en el Menú realizado....
Salu2