Most (maybe all) modals have two meanings, a deontic one about the real world (including social things like obligations), and an epistemic one about somebody's knowledge or expectation of things.
So I must go is deontic: I am stating that there is an obligation on me to go. But He must be on his way is epistemic: there is no obligation on him, the speaker has deduced, or is otherwise sure, that he is on his way.
When a modal is used with have, the meaning is very often epistemic: He must have gone cannot be deontic (we have to express the deontic meaning in other ways, such as "He had to go", or "He was obliged to go".
Other modals can take either meaning in the perfect, depending on context: I should have seen it is deontic, but I think he should have got there now is almost certainly epistemic.
So your examples are both epistemic "must".
But in answer to your main question, modals with "have" behave like past tenses, but not necessarily like (present or past) perfects: there is not necessarily any present relevance. "He should have seen it" can correspond to either "he saw it" or "he has seen it".
(Note also that epistemic will shows that will is indeed a modal, not a marker of "future tense": He will have seen it by now is epistemic and explicitly not future: it means something like "I conclude that he has seen it by now").