potrzebujesz tylko prostego zapytania z prefiksem. Twoje wyrażenie regularne to ^ + searchKey. Ponadto ten formularz pozwoli mongodb na użycie indeksu w nazwie.
var spec = new Document("Name", new MongoRegex(string.Format("^{0}",searchKey), "i"));
collection.Find(spec)