The Tleilaxu don't worship Leto II, they view him as a prophet of their God, the same monotheistic Abrahamic deity worshipped by the bulk of present-day humanity.
They had waited millennia for this time, his people. Waff savored the
moment now. All through the bad times of the Prophet Leto II (not God
Emperor but God’s Messenger), all through the Famines and the
Scattering, through every painful defeat at the hands of lesser
creatures, through all of those agonies the Tleilaxu had built their
patient forces for this moment.
We have come to our moment, O Prophet!
Heretics of Dune
As to when, it seems likely that they came to this belief sometime during his elongated reign. We don't get any more info in the books (since the first Bene Tleilax Master that we get to spend any time with is after Leto's death) but we do know that he had extensive dealings with them, more than sufficient for them to observe his ability to determine the future.