“Fed up” as a phrase comes from feeding livestock up to their fill. It’s very similar to how you would say “filled up”. So the upness comes from raising the level up to the limit.