If Thelyron is really gone you most likely checked his hut at the far southeast map end before finding the evidence. In this case you will see him short before the end game in Cyseal, Evelyn will be in her lair.

Regards,
Thorsten