Как вы устанавливали приложение? Через менежер пакетов или скачали с официального сайта и далее через dpkg -i package_name ?
Если вы скачали Telegram прямо с веб-сайта, ваша система управления пакетами не знает об этом, и вам придется удалить файлы самостоятельно. Вы можете найти их в ~/Downloads, но, возможно, они в другом месте, например в /opt. Если вы использовали Telegram, вы также можете найти автоматически созданный каталог в ~/Downloads под названием Telegram Desktop, который содержит файлы, которые вы загрузили из сообщений Telegram. Также может быть скрытый каталог в вашем домашнем ~/.TelegramDesktop. Вы можете удалить Telegram, удалив все эти файлы и каталоги.
Можно так же запустить такую команду, что бы определить файлы и каталоги, установленные приложением:
sudo updatedb && locate Telegram
Если вы ставили программу через Atareao PPA, тогда можно удалить, снеся при этом сам PPA:
sudo apt remove telegram
sudo add-apt-repository -r ppa:atareao/telegram
Так же существует удобная команда ppa-purge для "правильного" удаления PPA и зависимостей:
sudo apt install ppa-purge
sudo ppa-purge ppa:atareao/telegram
Если вы поставили Телеграм через snap-пакет telegram-sergiusens, то удалить можно так:
sudo snap remove telegram-sergiusens
Кстати, если запустить Telegram, можно воспользоваться утилитой lsof что бы понять какие файлы и каталоги задействованы приложением:
lsof|grep Telegram
В моем случе эта команда показывает путь
~/.local/share/TelegramDesktop/
