Few have explored the extremes of outdoor life further than Bavarian film-maker Werner Herzog. As Herzog himself has said: "Every man should pull a boat over a mountain once in his life."

The British Film Institute published its 10-yearly poll of the most important movies. The name of Werner Herzog does not appear on it. Not 'Aguirre Wrath of God', not 'Fitzcarraldo', not even 'Even Dwarfs Started Small'. How can this be? Well, the list is compiled by movie-makers and critics, people whose working life is spent indoors under cover – and Herzog is the all-time chronicler of outdoor life, the implacable nature of Nature and the odd, intriguing ways we outdoor types interact with the world.

I was casting about for an excuse to involve 'Grizzly Man' and 'Scream of Stone' in this series supposedly about Classic Mountain Literature. That's how I discovered that Werner is, indeed, a long-distance walker and a writer too. Munich to Paris, in winter conditions and unsuitable shoes, in November and December of 1974. He received word that film critic and mentor Lotte Eisner was seriously ill in Paris. Herzog set out "in full faith, believing that she would stay alive if I came on foot".

It's a walk which Google reckons (by the Google-suggested best walking route) is 777km with 4500m of ascent; heading through the Black Forest then over the hills of the Vosges. Herzog hikes it without a map, until he buys a road map at a petrol station. As night falls, he breaks into a barn or an empty holiday home. He does carry a little cash, for when he can bring himself, soaked through and stinking, to enter a shop. Otherwise he feeds himself by begging, or scavenging sugar beets from the muddy fields.

Five hundred metres into his walk, he pops into the hospital to visit an actor damaged jumping out of a moving VW van while making a Werner Herzog movie; also to get his Tarot cast.

Grass is flat with mud

A man chases a woman

In a rain-soaked field

Reading or re-reading an outdoor classic every month or so for this series throws up some interesting links. Having been with Basho on his narrow road to the deep north, I started to notice haiku-like messages in Herzog as well. I don't suppose that Herzog was even aware of his Japanese predecessor: the very slight adjustments towards haiku format are mine. The original is in German: the translators are his first wife Marje Herzog and Alan Greenberg.

The train swirled up paper

dry paper swirled a long time

then the train was gone

As with Matsuo Basho, loneliness is the base note of his outdoor experience. Tricky question, is this Herzog or Basho?

Utter loneliness

a brook is my walk partner

grey heron flies in front

Apart from evoking the pity and the terror, one thing us walking writers do is: we supply some commentary on our kit. "My boots were so solid and new that I had confidence in them." And, just as any more experienced long distance walker will be expecting: "Day 2, preliminary problems with my boots… they pinch." And by Day 3 the blisters are starting to build. "I had no idea walking could hurt so much."

On Day 5 he has to buy a newspaper to find out what day of the week it is.

Why do some of us set ourselves these sorts of extreme challenges? What Werner Herzog understands is the power in all this of the story. The stories we tell ourselves, about ourselves, and that we then present as ourselves to the outer world. These stories need to be vivid, and vigorous, with carefully crafted plotlines. Thus when choosing to go up a mountain, it tends to be one that other people have already heard of, whether that's Everest, or Ben Nevis, or Cat Bells. And Herzog is a master of lively and exciting life-stories. On one film shoot even more accident prone than usual, he pledged to jump into a cactus patch if the cast and production team didn't further injure themselves while completing it. They didn't – so he did. "No, it was not self destructive to jump into a cactus. I was just giving them a little fun." To encourage a friend who constantly talked film-making to actually make a film, Herzog promised to eat his own shoe: the result is recorded in the documentary "Werner Herzog Eats his Shoe".

The high point of Herzog's own walk isn't especially high. The 710m Huehnersedel, in the Black Forest, is noted for its mountain bike trails and view over the Rhine. Herzog crosses it under hail, sleet, snow and 100mph winds.

That was the only hill climb in his trip: even Matsuo Basho took in more mountains. Because, disappointingly, Herzog was not the leader of the 1951 expedition to Annapurna – that was Maurice Herzog, who was French not German. Werner Herzog's mountaineering took place in the movies.

Of Walking In Ice is only 66 pages. But if you reckon every 17 syllables as one haiku – that still makes for a big read.

A glove in the field

wet, and cold water lying

In the tractor tracks

Yes, the 'loneliness' haiku was Herzog's one, though Basho's on the same subject is a close match. And when, after 21 days on the road, he arrives in Paris, Lotte Eisner is indeed still alive.

All the top walking writers crowd onto the back cover to praise this book. Robert Macfarlane (Mountains of the Mind) calls it a weird, slender classic. For Iain Sinclair (London Orbital) it's a fugue and an absurdist comedy. Helen Macdonald (H is for Hawk) says it has the eerie power of the best fairy tales.

The new documentary Werner Herzog: Radical Dreamer is out now: