Hi Sparafucile! Long time no see!
Herbert described a truthsayer as one who went into a semi-hypnotic trance that was induced by one of the awareness spectrum narcotics (of which spice was one, revealed to the BG after the Ceremony of the Seed) where the user of the drug was essentially hyperaware of the speaker's "petit betrayals of deliberate falsehood." What I think this means is that there is not a oracular or computational element to it. The truthsayer is merely aware of certain "tells" such as increased heartbeat, increased perspiration, fluctuations of voice, movements of eye, etc.
It is true that the truthsayers we met in the books were RM's, but RM's did not necessarily have prescience (although Mohiam did), and until Anteac, IIRC, there were no mentat RM's. At least Mohiam was not a mentat, and she was our first truthsayer, so it would have had to be something else. I don't recall FH saying pointedly that Moham's light prescient abilities helped her as a truthsayer, but even if she only had a light Guild-like linear prescience, I cannot see it being a hindrance, no?