The next lines explain it "quite well":
Who broke our fair companionship,
And spread his mantle dark and cold,
And wrapt thee formless in the fold,
And dull'd the murmur on thy lip,
And bore thee where I could not see
Nor follow, tho' I walk in haste,
And think, that somewhere in the waste
The Shadow sits and waits for me.
The Shadow is death, (almost) obviously.
Now about "feared of man" - it is not common in everyday speech nowadays. We would say:
"the Shadow feared by man"
man being afraid of the Shadow.
You can test this using "bears", "vampires", "werewolves" instead of "the Shadow" to the same conclusion.
"Man" in this context does not refer to any person in particular, but to people (in general). As in:
People are afraid of death.