① Grammar pattern
The grammar pattern used here is:
V(ない form, and drop the い) + なければならない
which means "must V", where V is any verb in the plain negative form (ending in ない) . First drop the い and then add なけらばならない
食【た】べない → 食【た】べな →食【た】べなけらばならない。"Must eat".
行【い】かない → 行【い】かな → 行【い】かなければならない。"Must go".
散歩【さんぽ】しない→ 散歩【さんぽ】しな → 散歩【さんぽ】しなければならない。"Must stroll".
② The meaning of 失礼【しつれい】する
失礼【しつれい】する means "to be rude", but in some situations it also means "goodbye" or "to leave". For sure, this meaning comes from the fact that leaving someone may be considered rude, no doubt here, but I would think of it as a set phrase to say goodbye. In fact, when Japanese people end a phone call in a formal situation, they use 失礼【いつれい】します as a farewell word.
③ 〜んです
Just for the sake of completeness, this grammar attached at the end of the sentences has several usages, in this sentence it adds the nuance of "the fact is...". There are many explanations in this in this site, for example this one.
Therefore, according to the points ① , ② and ③, the original sentence can be translated as
Excuse me, the fact is that I have to leave.
as you pointed out. Breaking it down:
a) The "have to" part corresponds to the conjugation なければならない as explained at ①.
b) The "leave" part corresponds to the meaning of 失礼【しつれい】 as explained at ②.
c) The "Excuse me" part, though not appearing explicitly, is present in the fact that "to excuse oneself" is an idiom that can convey "to leave" in a polite way, both in English and in Japanese, as desseim pointed out in a comment.
d) The "the fact is" part corresponds to the final 〜んです (see ③).
As a conclusion, I agree with user3856370's answer that
Really you should think of なければならない (nakerebanaranai) as a unit in its own right.
It will make it easier to wrap your head around this grammar point.
Hope it helps!