The Setup instructions on the campaign card for Passing of the Grey Company allow the first player to raise everyone's threat by 1 and add Anduril to your hand from your deck. Would that be before draw your setup hand? So, if you decide to mulligan, Anduril goes back into your deck? Or do you do this afterward, immediately before you would do the quest card setup instructions?

The Core Set rulebook says you draw (+ mulligan) your initial hand before you arrange and place the quest cards. The Saga rulebooks say you place the campaign card next to the quest deck (and then follow the setup instructions), which won't be on the table until after you've drawn your setup hand. I don't think you'd lose Andúril to a mulligan.

Agreed. Step 5 of the set-up is drawing your hand, including a potential mulligan. Step 6 is setting the quest/campaign Cards (so you shouldn't even know about the possibility of getting Anduril when faced with the Mulligan Option, therefore I see know reason why it should get shuffeld back) and Step 7 following the setup instructions.