Would be creating menus totally in views reasonable?
Yes. That's the point of views, you should not worry about performance at that point, just build the menu and if later you find that performance is worse than expected start taking a look at this question, there is a big amount of information on views caching. If you need more you can also go here to find more information on caching and performance in general.