GNOME menu editing is not enabled by default, and I haven't found a way to get menu editing in GNOME. You can try the following as root:
cd /usr/share/applications
if you then do
ls * you will see .desktop files take a look at one of these files to see the setup. You could try this, it might work.
Open up your favorite text editor, you will probably have to do this in you home directory, unless you login as root graphically. Anyway try this and see if it works:
[desktop]
Encoding=UTF-8
Name=Game Name
Comment=eg. First Person Shoot
Exec=/path/to/game/executable
Icon=/path/to/icon/to/use.png
Terminal=false
Type=Application
Categories=Applications;Game;"Power Game";
StartupNotify=true
Save this as gamename.desktop, if you are root you can just save this directly to /usr/share/applications, if you are a user save to your home directory then:
su
chown root:root gamename.desktop
mv gamename.desktop /usr/share/applications
Logout of Gnome and then back in, the game should now show up in your Menu for all users.
I don't know if this will create a submenu, I haven't tried creating any new submenus.
HTH