Nope, it is not a matter of formality or frequency. But yes, it is a matter of meaning. "실례합니다" means only "Excuse me", whereas "실례지만" means "Excuse me, but". If you say "실례지만", you should add some more things to say because like I said it means "Excuse me, but". So, for example, you can make a sentence like this: "실례지만 지금이 몇 시죠?" = "Excuse me, but what time is it?" I'm sure you already know it also makes sense if you say "실례합니다. 지금이 몇 시죠?" because it also makes sense in English("Excuse me. What time is it?"). It is just that 실례합니다 doesn't have a conjunction, "but". To add one more thing, when you are in the subway and want someone to step aside a little bit, you say "Excuse me" since "Excuse me, but" is quite awkward to replace "Excuse me". Just like this, you would want to say "실례합니다" not "실례지만".

Almost same. 실례지만, 지나가도 될까요? (one sentence) 실례합니다. 지나가도 될까요? (two sentence) 실례지만, 전화기 좀 빌릴 수 있을 까요? (one sentence) 실례합니다. 전화기 좀 빌릴 수 있을까요? (two sentence) 실례합니다. + 그렇지만(meaning is though or but) = 실례지만