Look in your home directory for a hidden folder /.config and look in it for a telegram configuration file. Even when you purge a package the home directory is not touched.
@anon42388993 is sort of on the right lines. I presume the desktop launcher is still visible in the menu or dock?
Open Caja and press CTRL+L, then copy and paste this address:
~/.local/share/applications
Start typing "telegram" and it should jump straight down to a telegram launcher.
Delete any telegram entries and poof, it's gone!
It's likely as you've ran it locally, the program decided to add a desktop launcher manually for you so it shows up in the menus. This is just deleting that "shortcut", even though it's gone from your system.
Telegram is also available to install from the Software Boutique too.