That's normal... especially in Erothin and Ostian the performance is really bad. E.g. I get around 10 fps in Erothin and maybe 15-20 in Ostian.
But in the wilderness and in dungeons/interiors the performance should be fine.
The reason is the engine, wich isn't optimized to run with such a high number of objects. Just look at the citys. In Oblivion they are seperate cells, so they are not loaded with the landscape around.
But in Nehrim almost everything is done within a single exterior. Also, the engine only uses a single cpu-thread/core, so multicore-cpu's won't better the performance (the gpu isn't the problem).
You can tweak Nehrim a little bit by activating the dual-cpu usage and by giving it more ram. The settings can be found in the Nehrim-launcher-->settings--->performance.