Let’s start by assuming that each character is one syllable. Below are the simple steps that lead to the solution.

1. Character 山 and syllable ‘shan’ are the only ones that occur three times in the list, so they must correspond to each other. Note that the syllable ‘shang’ in Shang-hai is different from ‘shan’.

2. The only word that can correspond to 天山 is Tian-shan, so 天 corresponds to the syllable ‘tian’.

3. The other two words with ‘shan’ are 山西 and 山东, so the second characters correspond to either ‘xi’ or ‘dong’ (Shan-xi and Shan-dong). The syllable ‘dong’ occurs only once, while ‘xi’ also appears in Mexico, there is only one word that fits: 墨西哥. Thus we conclude that 西 is ‘xi’ and 东 is ‘dong’.

4. By searching for 天 character we notice that Tian-jin must be 天津. We just matched five words: Tian-shan, Shan-dong, Shan-xi, Tian-jin, and Mexico.

5. 3 syllable 巴拉圭 and 2 syllable 巴黎 words have the same first character. After taking into account all what we already know these two words must correspond to Pa-ra-guay and Pa-ris.

6. We are left with three last words to sort out: 南京, 北京, and 北冰洋 and Bei-jing, Nan-jing, and Arctic ocean. Apparently 京 = ‘jing’ and 北冰洋 is Arctic ocean.

7. This is the last step and we need a hint. Arctic ocean has too many syllabi, so we can suggest that in this case these three characters 北, 冰, and 洋 were selected by meaning (not by pronunciation). And if we recall that Bei-jing is the 'North capital' and Arctic is a region near the North pole then it is natural to suggest that character 北 means 'North', 北京 is Bei-jing (North capital) and 南京 is Nan-jing.