>Did Herbert have a plan for this combo, or was he just making up some future backstory?

It has been a very long time since I read all the novels so I can't recall all the details. It is a major plot point in book 5 "Heretics of Dune" zensunni leads to the alliance between the Bene Gesserit and the Tleilaxian's. The Tleilaxu follow a strict interpretation of the religion in secret and during a meeting between the faction leaders one of the reverend mothers is able to deduce this from their speech patterns and manipulate them into an alliance which has some ramifications.

Considering the Tleilaxu aren't introduced until book 2 (I think) I assume it was planned out ahead of time by Herbert.