What OS and video card are you using? I don't think you can change it in Gens, if you look at the manual it only mentions full screen at 640x480, and nowhere in the program/help files/config do I see where you can change that.
When I first installed XP, I couldn't go lower than 800x600 with my GeForce II MX.
I installed
Multires, which is a handy little on-the-fly resolution switcher, that if I remember correctly, automatically enabled 640x480 switching on install.
If that doesn't work, it's probably more a matter of finding a site that show how to key custom resolutions into the registry (be careful). There well may be a custom tool for your card that would make the process easier that can be found on those trendy high-end 3D card tweaking sites...
Try checking on your video card manufacturer's site if nothing else.