If you only deleted the program menu shortcut the program will remain fully installed. You only need to find the file that is run by the missing shortcut and make a new shortcut. Did you check the Recycle bin for the shortcut you deleted? Otherwise you need to find the program folder. Unfortunately it may not even have the word felix in it at all so it can be hard to locate.
If you do find it I would definitely NOT delete the folder. It may contain the uninstaller which could be the only way you will ever remove the program completely from your system. You may have deleted a whole Felix folder from the start menu including the shortcut to the uninstaller which it may have contained.
Most programs CANNOT be uninstalled by simply deleting their program folder. When a program is installed, very often if will write information to the registry. Usually the registry entries are checked to determine if the program is already installed. This is done because the user may choose to install the program in a different location from the default. An install log located in the program folder often holds the information about the registry entries. Without this information it can be very difficult to find those entries.
If you do find the Felix program folder check if it contains a file called unwise.exe because this is a very common name for the uninstaller. It is short for Uninstall Wizard and it is usually unwise to run it because it will remove the program.
Bookmarks and Favourites are irrelevant.