It seems to be capped at 50% for me. Is this normal, or am I missing something obvious?
The more assassins you have stationed in a city, and the higher their level, the higher your maximum influence in that city is. If you enter the assassin management interface, you can see it listed as current%/maximum%. Three or four high-level assassins is enough to get it close to max. (There's really no reason not to fill them up with your low-level assassins constantly - a fully upgraded city will send them all to level 6 or 7 in a day).