Some algorithms are hard to express in pure, strict functional settings. (There's even an impossibility theorem for a few algorithms, but that theorem doesn't apply to pure, lazy languages.) That being said, the worst asymptotic slowdown is logarithmic---because you can always simulate random access memory.

On a more practical side, you have constant factors to worry about, and things like caches. Look at eg Don Stewarts work for how to deal with these in a functional language.

(And, in practice, there's no shame in throwing in the towel and either interfacing with other languages, or even switching to them.)