Using すみません is very important in Japanese and as you've noted, it is used in a lot of contexts. (There have also been many questions here about it).
A few of the relevant ones to look at as references:
What is the difference between すみません and すみませんでした?
Using すみません instead of ありがとう
Usage of すみません (sumimasen) versus ごめんなさい (gomen'nasai)
Is there a difference between すみません (sumimasen) and すいません (suimasen?)
すみません is the polite negated form of すむ (済む). 済む means to "complete or end something." At least to me it was helpful to learn this, because etymologically what すみません or すまない (it's less polite cousin) mean is "I was inadequate" or "I was unable to complete [x] / do [x]"
JDICT translates it as
excuse me, pardon me, I'm sorry.
Goo's dictionary defines it as
The etymology of being the polite negation of 済む *plus* a phrase
that is employed to express thanks, imposition of a task, or that
I've done something wrong.
This is not exactly identical to the English (or may be just my American English?) "I'm sorry" as in "I feel emotionally terrible for having done this" and "I regret having done this" in that in Japanese this phrase is used all over the place for all sorts of things for which I have zero feelings at all.
The two examples you picked don't seem like the clearest ways to understand すみません but the phrase is used a lot every day.
For the bank example, my sense as to what's happening is Ieda-san is apologizing that he's about to make the clerk do work for him (or alternatively that he's so blandly unidentifiable that the clerk has to yell for his name rather than knowing who he is). Alternately, he is apologizing for not having been able to take care of the matter himself and thus forcing other customers to wait.
For the department store example, I would imagine the clerk is apologizing for making her do something, and she in turn is apologizing for making him do something.
- Apology - I am sorry I could not accomplish this.
- Thanks and apology - I am sorry I could not accomplish this [if you want to be thankful add ありがとうございます]
- Making a request - "I can't accomplish this on my own so ..."
- Getting attention - "I am sorry that I can't do this on my own and have had to get your attention"
- Taking leave - "due to my inadequacy, I can't stay until the end of what is going on"