Have you looked in every folder in your phone for the app?
It's not possible to create an icon. The only way to get an icon back is to reset the phone. Sometimes restoring to factory defaults will bring it back. Another way is to restore a settings backup but that doesn't always work.
I dont think you can add an icon into any of the application menus - or at least I cannot figure it out.
You can however add it to one of the widgets on your home screen in the application shortcut.