Никита

На мой взгляд лучшим решением будет прочитать большой файл names.txt в list и, соответственно, держать его в памяти.

Ну а дальше дело техники. Читаем построчно файл с городами. Для каждого города создаём папку с соответствующим именем. В папке файл name.txt. В него осуществяем построчную запись случайной строки из исходного файла с проверкой на дублирование.

Структуру файла cities.txt я принял такую: [город]|[количество строк для города]

москва|1000
санкт-петербург|1100

__author__ = 'kascode'
from random import randint
import os

source = open('names.txt', 'r')

sourcelines = source.readlines()
sourcelineslen = len(sourcelines)

def readCities():
    with open('cities.txt', 'r') as f:
        citylines = f.readlines()

    citieslist = []
    
    # заполняем список данными в формате [['город'], ['число строк']] 
    for line in citylines:
        citieslist.append(line.split('|'))

    return citieslist

for city in readCities():
    # создаём папку с именем города
    if not os.path.exists(city[0]):
        os.makedirs(city[0])

    file = city[0] + '/name.txt'
    cityout = open(file, 'w')
    written = []        # массив записанных строк

    # записываем столько строк, сколько указано для города
    for i in range(1, int(city[1])):
        # берём случайную строку из исходного списка
        sourceline = sourcelines[randint(0, sourcelineslen-1)]
        
        # берём новую пока не найдём не дублирующую
        while sourceline in written:
            sourceline = sourcelines[randint(0, sourcelineslen-1)]

        cityout.write(sourceline)
        written.append(sourceline)

На моей машине обработка файла в 10000000 строк длиной 10-50 символов заняла 0,21с.