A menu uses a normal MPEG-2 just like the DVD does.
A recent set of menus I made, for example, are video clips from the show. Many DVD authoring programs require progressive video on menus, not interlaced, so you have to IVTC your interlaced video in advance. I did it in TMPGEnc Plus. I encoded new progressive MPEG-2 files. Because NLEs work best with low/uncompressed AVI files, I used
VirtualDub to convert the MPEG-2 videos into uncompressed AVI files. Those videos were imported into Adobe Premiere, an NLE. I added some Adobe Photoshop PSD files with alpha layers to create the motion menu. The clips were edited into a new menu. The only thing I did in the authoring program was added the little red select buttons on top of the video.
Authoring applications do not "make menus" but rather assemble what you give it. In this case, for a full motion menu, you need to give it a video clip ready to use. There are other ways for simpler types of motion (thumbnail motion, for example, or background motion only. But of course, those don't look as good.
Something like Ulead VS is not made for episode-style DVD authoring. That's a piece of software a soccer mom uses to create a simple DVD from her DV camera video of little Timmy's baseball game. It makes assumptions about your source material. It's not made for TV recordings or short clips. My method is good for any source, and I mostly do VHS transfers and multi-clip/multi-source recordings.