There are 4 possible combinations and arrangements I'd like to compare and contrast:
- Plant trees as much as possible.
- Plant trees as many as possible.
- Plant as much trees as possible.
- Plant as many trees as possible.
As far as I'm concerned (native speaker but not necessarily equipped to explain English to a non-native), 1 and 4 are definitely correct, 2 could be correct if spoken with a pause between "trees" and "as", and 3 is wrong.
Choice 3 is wrong for the reasons you've already mentioned: "Tree" is a countable noun so it must be modified by "many" rather than "much". This same reason is why choice 4 is correct.
Choice 2 would only be correct if written with a comma to indicate that "as many as possible" is an afterthought.
- Plant trees, as many as possible.
In other words, the speaker just said, "Plant trees." and after saying that, decided to add, "as many as possible." The sentence isn't technically grammatical but certain liberties are allowed in spoken language since thinking can be slower than speaking.
Regarding choice 1, I believe it is also correct but it conveys something slightly different from choice 4. In choice 4, the sentence is broken down like:
- (Plant) (as many trees as possible).
I may be wrong about this but I think "as many trees as possible" is a noun phrase acting as the direct object of plant. This sentence is telling the listener to plant something. It is telling the listener to plant a lot of trees.
Choice 1 on the other hand
- (Plant trees) (as much as possible).
In this sentence, "as much as possible" is an adverbial phrase modifying "Plant". This sentence is telling the listener how often he should plant trees. It is telling the listener to plant trees often.