Entiendo, lo que quieres tener los subitems a 2 columnas, eso lo puedes hacer cambiando tu theme, te puedes fijar del código del ejemplo que muestras. No sé si habrá algún plugin que te lo haga gratis, este lo hace y son sóo 16 dólares http://wpmegamenu.com/
Si te resulta complicado lo que haría es en vez de 2 columnas agruparlos en subcategorías para que no se haga muy largo.
Saludos