Tom undoubtedly figured out that it would be only a matter of time before Michael had Fredo killed. Tom had been around long enough, and was smart enough, to know that Michael would never give a pass to an enemy. And let's remember that, just before Fredo got it, Michael reminded him of the above when he demanded that Hagen support him in the deaths of Roth and Pentangeli, despite Hagen's protestations.
As for Michael's relationship with Hagen: Tom was the Don's choice for consigliere, not Michael's. Sonny, not Michael, brought Tom home and treated him as his brother. I also believe that Michael may have blamed Hagen for Sonny's death, for Kay's abortion, and for the near-miss Michael had with five counts of perjury.