Learn Icelandic: Skeljarnar voru alls staðar þegar við gengum um strandlengjuna. - The shells were everywhere when we walked along the coastline.

It is literally a fossilized genitive phrase meaning "of all place" (alls is the genitive of allt, and staðar is the genitive of staður). Even though it is two words, it acts as a single, fixed adverb for static location, meaning it never changes form to match gender, case, or number.

Since gengum is a verb of motion, shouldn't we use a directional adverb instead of the static alls staðar?

No, because the shells themselves are stationary. The adverb alls staðar describes where the shells were located (Skeljarnar voru...), not the direction of your walking. If you were physically scattering shells everywhere as you walked, you would need a directional motion adverb instead.

Why does the preposition um take the accusative case in um strandlengjuna? I thought it meant "about".

While um often means "about" in the context of talking or thinking, when combined with a physical motion verb like ganga (to walk), it translates to "around," "through," or "along." In all these usages, um always governs the accusative case, changing the feminine noun strandlengja to strandlengju (and strandlengjuna with the attached article).

What is the base form of skeljarnar? The -jar ending looks a bit tricky.