Not only did he convince Mat that they were in danger, he also reminded him that they would probably never admit to needing help until it was too late (for anyone other than a ta'veren like Mat, anyway). Remember the way Egwene always deflected Rand's attempts to learn about Salidar? It made it very likely from his point of view that she may have been exaggerating about the number of Sisters gathered there. It's a reasonable conclusion, given the circumstances, and also likely influenced his view on the Rebels for several books, not to mention that Egwene never deigned to tell him that she had coerced Mat to go south with Elayne. Remember when he had himself smuggled into Caemlyn because he thought Mat and Elayne may have arrived already?

As for Mat/Aviendha/Elayne; Mat needed less than a minute of Avi's body language to realize that she fancied Rand. Add the knife and her expressed need to see Elayne, and what else was he supposed to bloody think?