Then again this is dealing with system-wide performance. Application-specific performance should be significantly less of a problem to fix.
I think the jobs that are simply "here is this function, make it 10x faster" would be pretty rare, since usually people don't know what part of the code is going slow. A lot of the times they'll guess "X, Y, Z is making it slow" but without a real performance analysis patching stuff all over the place just doesn't pan out.
I've met a guy who runs a company of about 6 programmers doing this, has more work than he can handle and has difficulty finding good enough programmers. I think they're mainly C++ but were recently trying to find a C# guy.
So it's in demand, but you've got to know where to look.
As an example of embedded programming, do some timing critical work with microcontrollers and you'll find all sorts of fun optimization problems. Recently I had an algorithm that took 13 microseconds to execute but needed to do it in 11 (there was another interrupt coming!). I got to have a good time with the debugger, understanding optimization levels used by GCC, reading lots of assembly, and playing with a logic analyzer. It's quite fun, actually.