I have exactly the same problem. A few containers running (gitlab + registry), volumes about 2GB overall, But /var/lib/docker/overaly directory is really huge >37GB and removing old containers, images, etc. doesn’t help.
Also I can’t upgrade my docker because it’s a part of CoreOS 1520.6.0 stable release and it can only by 1.12
Same situation happens on another instance with another set of containers (nginx+php+postgres). I felt like it freed some space one day when instance and docker were accidentally rebooted but I’m not sure if it’s a solution