Can Rumble, Hotheaded choose a Mech token to recycle? If he does, where does it go?

Yes, he can. This is a minor gap in the rules. Main Deck cards are recycled to the Main Deck and runes are recycled to the Rune deck, but tokens aren’t actually either of those things. We’ll be clarifying in a future rules updates that tokens “inherit” the recycle destination of their type(s), so a token that’s a unit or gear is recycled to your Main Deck just like any other gear. It then vanishes, as tokens do any time they leave the board, but it still counts as “the unit you recycled” and Rumble can check its Might.