Bear in mind that neither batteries nor voltage converters are 100% efficient.
a) You have to put more into a battery than you get out. If you've an 1100 mAh battery, you will have to put about 1250 mAh into it to fully charge it.
b) The voltage converters are only about 90% efficient, and you are converting twice - once from backup battery voltage (3.7 or 7.4V, usually) to 5V USB, and once back from USB to whatever your device battery takes. So call that about a 19% loss.
c) A 5000mAh battery pack will give 5000mAh output under ideal conditions and having been fully charged properly in the first place, but it's quite likely that you'll only get 4500 mAh out of it. (eg a 2500 mAh AA NiMh typically reports 2200mAh on my charger). It's usually a combination of the battery feeling a bit less than perfect, and the charger stopping charge a bit early to avoid damaging it.
It can help to leave the charger running for a couple of hours after the fully charged light comes on - some chargers switch over to a slow trickle/top up charging rate rather than just stop.
Combine these, and 4500 * 0.81 = 3645 / 1250 = 2.9
So assume that your 5000mAh backup battery will charge your 1100mAh phone almost 3 times. You may do a bit better, but don't count on it.
It is not the case that remaining capacity in the charging battery has to exceed the capacity of the charged battery. Switch mode converters can be very good at getting every last bit of juice out of a battery, which is why they are generally set to turn off before the battery is run slow empty it gets damaged.