Finish dwarven area or elves?
 

I have sealed the deal with dwarves and done some clearing of areas at dwarves but I seem to be finding more and more areas there. When I returned with deal to king it asked me to go to elf lands.

Now I am wondering what is "right" (easiest) order to do stuff? Should I clear areas at dwarves I haven't yet explored, underground sea and where train goes (and possible areas where I can get for those two places)? Or should I go after elves?

Well, there is really no "right" order to do stuff. The underground sea has a few battles that you may find overpowering or even impossible even at normal level and leads ultimately to the demon's world (demonis) where the opposition is very tough.
The elves have some encounters that can be won after the dwarves but some should be avoided. However you can get some nice goodies (and units - emerald dragons spring to mind) if you explore there and avoid the tougher mobs. Finish off all battles/areas that you can without sacrificing a lot of your troops - that's the strategy that I follow, and it has proven solid so far. That means that I go back and forth quite a bit to finish off fights that were too hard earlier on, but at least I keep most of my hard to find troops intact :).

I cleared underground sea now. And working on the place where train goes. I guess I clear those and they go check elves. Did quick peek on demonis. It didn't look impossible but I really need to find some new units to replace my shamans. They are starting to grow thin and too lazy to go all the way to pirate islands to resupply.

be sure to save prior to going back to the orcish embassey after the dwarven king's quest since it turns hostile again...