Mdthbs

I've just heard the phrase shitsurei shinakereba 
naranaindesu used as Excuse me, I have to leave.
The explanation said it literally translates to If I don't leave, it won't do,
but I need help on breaking it down precisely.

What does each word mean and how does the grammar work here?

失礼{しつれい}しなければならない

失礼 (shitsurei) is "rudeness".

失礼する (shitsurei suru) is "to be rude"

失礼しない (shitsurei shinai) is the negation "to not be rude".

失礼しなければ (shitsurei shinakereba) is a conditional form of the above "If I am not rude"

失礼しなければならない (shitsurei shinakereba naranai) I'm now sure how to break down ならない meaningfully but in this context it kind of means "It's no good".

So literally the whole thing means "If I'm not rude then it's no good". Really you should think of なければならない (nakerebanaranai) as a unit in its own right. This attaches to the negative form of the predicate and means "must do"/"have to do" etc, which is the logical implication of the expansion "If I don't do, then it's no good".

Overall then, the sentence means "I have to be rude", which is what you might say if you were leaving.

① 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 if 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 aplearing explicitly, is present in the fact that it is used 失礼【しつれい】する, rather than 行【い】く. The usage of this word makes the sentence polite, as explained at ② as well.

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!