URL rewrite of localisation with nginx
This answer should help:
https://serverfault.com/questions/488444/nginx-rewrite-convert-querystring-to-path/488480#488480

I would try something along the lines of:

location @drupal {
  if ($arg_lang) {
    rewrite ^(.*)$ $arg_lang/$1? permanent;
  }

  rewrite ^ /index.php;
}


The above assumes that requests with ?lang=XX do not have any other arguments, and that the request does not already have the language prefix in the page request (ex: /XX/node/123?lang=XX).