Ok, I solved it as follows (inspired by this postthis post) - might be helpful for someone else...
The idea is to start from the back, removing more and more tokens between '/' from the path until we find the lowest level site URL, which we then use to instantiate the correct ClientContext for the given folder url. The folder itself can then be referenced using GetFolderByServerRelativeUrl(), but be aware that the argument is relative to the server, not relative to the site.
private bool GetSharePointContextAndFolderByUrl(string url, ref ClientContext context, ref Folder folder)
{
Uri uri = new Uri(url);
string[] tokens = uri.AbsolutePath.Split(new char[] { '/' }, StringSplitOptions.RemoveEmptyEntries);
for (int i = tokens.Length; i >= 0; i--)
{
string absUrl = string.Join("/", tokens.Take(i));
string siteUrl = string.Format("{0}{1}{2}/{3}", uri.Scheme, Uri.SchemeDelimiter, uri.Host, absUrl);
ClientContext c = null;
try
{
c = new ClientContext(siteUrl);
Folder f = c.Web.GetFolderByServerRelativeUrl(uri.AbsolutePath);
c.Load(f);
c.ExecuteQuery();
context = c;
folder = f;
return true;
}
catch (Exception e) { }
if (c != null) c.Dispose();
}
return false;
}