I can't speak for Scala, but the PM in Haskell and OCaml is a bit different since it's informed by the static typing. When patterns have variant types (i.e., x is either Foo, Bar, or Baz * int), it also checks for complete coverage. Same general concept, different flavor. Also very useful.
I mentioned Prolog in particular because its emphasis on unification and backtracking make it the most pattern-matching-centric programming language I've seen. Where other languages have pattern matching, it almost is pattern matching.
Also, there are well-known ways to compile pattern specifications into efficient decision trees, so while it's a very expressive abstraction, it's not necessarily an expensive one. If they're being constructed at runtime (as they are in my Lua library), you can generally get a big improvement by just indexing on the patterns' first fields and doing linear search thereafter.
The parent post mentions Prolog, which is a good example, but there are several others worth trying that frequently come up on HN; Scala, Haskell, F#, and Ocaml spring to mind.