I try to minimize my fast traveling in games. I Shadow of Mordor, I don't think I ever used it. I did it quite a bit in Skyrim, I think. It definitely hurts the world and its point of existence, unless it's a game where enemies stop spawning once it's cleared. At that points, it's just a left stick time sink. However, in a game where there will always be something going on between points, it's good to do things on foot.
But really, it seems we're at a point where, after years of complaining that some games are too linear (BioShock Infinite), people are getting tired of open-world games. Fetch quests and the like are just turning decent games into excessively long titles. Yes, a game can be too long. I don't want every game I play to feel like a job. A game that only takes 20-50 hours to complete (like Mordor and Sunset Overdrive) is fine. It's part of why I won't touch The Witcher, and part of why I'm not really bothering with Fallout 4--the second I get into it, it's all I play, and I have Destiny: TTK and Forza 6 still in their plastic, plus both Kingdom Hearts HD ReMix releases, Halo 5, and Battlefront I want to play.
Too many games, too little time, and a lot more (The Division, DOOM, Quantum Break, and I could go on) coming too quickly.