Thank you so much, I was battling with this all weekend, who would have thought this is all it took

Great to hear! Glad I was able to help

If you don't mind, I would also like to know how to create child collections, I tried using the collection keys create above as the provider key with no success

currently I have:

foreach (var subCollection in sec.Subsections) {
                var sub = this.MerchelloServices.EntityCollectionService.CreateEntityCollectionWithKey(EntityType.Product, collection.Key, subCollection.Name);
                this.MerchelloServices.EntityCollectionService.Save(sub);
            }

I had hoped there would be a createChildCollection method against the collection

Basically what you have to do, is create a second collection, and pass the ParentKey to that collection.

So in short:

var parent = merchelloServices.EntityCollectionService.CreateEntityCollection(
                    EntityType.Product,
                    Core.Constants.ProviderKeys.EntityCollection.StaticProductCollectionProviderKey,
                    "parent collection");

        var child = merchelloServices.EntityCollectionService.CreateEntityCollection(
                    EntityType.Product,
                    Core.Constants.ProviderKeys.EntityCollection.StaticProductCollectionProviderKey,
                    "Child collection");
        child.ParentKey = parent.Key;

        // Save the collections
        merchelloServices.EntityCollectionService.Save(new[] { parent, child });

That should do it