Creio que instalou o TeXlive pelo terminal ou da central de programas. O ideal é instalar da iso direto do site.
Mas tudo bem, isso não tem relação com o seu problema.
O pacote, está aqui:
https://ctan.org/pkg/soulMas como disseram, precisa instalar algum pacote do TeXlive que o inclui. Confesso que não sei qual. Pode ir tentando, ao invés de fazer o full como foi dito. Tente instalar:
texlive-extra-utils
texlive-generic-extra
ou algum outro que consegue com
sudo apt-get install texlive
e depois vá dando TAB pra ir lendo os pacotes possíveis.
Se tiver interesse, pode tentar usar o tlmgr que é o gerenciador de pacotes do TeXlive. Tente no terminal
sudo tlmgr -gui
pra ver se ele está instalado. (requer o perl-tk).
Até mais.