It's is an alarmingly common misconception that adverbs modify verbs. Or rather, a common incomplete understanding. Adverbs modify verbs, and also adjectives. They can also modify other adverbs, and sometimes a whole phrase - even a noun phrase. Mostly it's verbs, adjectives and other adverbs, though.
We can see that extremely here is an adverb, and modifies uphill. It is an adverb of degree, like very or slightly, which you are likely to have seen modify adjectives before:
This bit of grammar is slightly difficult.
This is a very tasty meal.
Thus, this battle is uphill to a great degree. Extremely usually denotes a greater degree than very, so we're looking at it being really, really uphill. This is metaphorical, of course, but it's strengthening the degree of the metaphor itself.
Your alternative, an "extreme uphill battle", would be two adjectives both modifying battle. It would be both an uphill battle, and an extreme battle, whatever that might mean.
I can see why teachers might tell people that adjectives modify nouns and adverbs modify verbs. It helps keep things simple, easy to learn and follow. But they really ought to correct that pretty soon afterwards to say that adverbs can modify adjectives as well. I mean, you've probably been using very since fairly early in language lessons, so I guess the teacher just never mentioned that very is an adverb...