If someone were to say that to me, what would I say in response? Do I thank them as well, for their service? Do I say "Sumimasen"?
恐れ入ります, used by itself, is a catch-all kind of word. It can be used either as a manner of apology or as a way of thanking a person. Therefore, the response to it really depends on the context in which it is being said.
相手にお願いごとや感謝を伝えるために使用するクッション言葉. "A 'cushion word' used to make a request of another party or to express gratitude."
If it is an apology for causing difficulty, a response along the lines of とんでもない or いいえ would be appropriate.
If it is showing gratitude, nothing really need be said. とんでもない could work in this case as well.
If it is someone apologizing for trying to get by you (which is not an actual apology, more of a request for you to make room) you could reply with 'sumimasen'.
As this expression would normally be used by someone in the service industry as a set expression which does not require or even expect response, it might actually be more polite to say nothing than to say anything. Just a grunt or a grin might suffice. This seems counter-intuitive to many Western cultures, but (in such a case) as the customer there is no real onus on you to reciprocate.