Why isn't my service found?
Not certain, but it sounds like your files may not be in the correct places based on your description.

The services.yml should be in the root of your module, not in a sub folder. 

Also, your service classes should be in a /src/ folder. It would be okay to have them in a /src/services folder if you want, but module namespaces in drupal start in the module's /src/ folder, not in the root; the reason for this is because drupal uses the PSR-4 naming conventions, which specify that structure. You can find more info about how drupal modules should be structured here: https://www.drupal.org/node/2156625