I encountered the same issue as recently. We have an appexchange app that handles deployments to different orgs using the Metadata api. Since we upgraded we got support cases mentioning that the deployment was running all good, no test failures reported but there was a code coverage error without specifying how much percent is missing (what is the normal behavior). And even if the org had more than 75% apex coverage.
After digging deeper in the issue we found the following cause:
Since Winter'19, API version 44.0, Salesforce is also checking code coverage on flow as soon as they are deployed as active. You can find the information in this release note: https://releasenotes.docs.salesforce.com/en-us/winter19/release-notes/rn_forcecom_flow_test_coverage.htm and https://releasenotes.docs.salesforce.com/en-us/winter19/release-notes/rn_forcecom_flow_deploy_as_active.htm
However the release notes state that this should be activated on the org and if not active the coverage is not applied. Again some deeper investigation from our side and we found that the setting is only available on production orgs (default false) but not on sandboxes. So deployments to sandbox always seem to calculate code coverage on flow or process builders. This was causing the deployments to fail unexpectedly, we found the actual error message in the FlowCoverageWarnings object received from checkDeploymentStatus method in the metadata api.
I'm not a 100% sure that what you encountered has the same cause, but I'm inclined to say it is.
I see only two options to avoid this in the future, either don't run tests deploying to sandbox (not really advisable) or provide test classes that cover process builder / flow logic so that it provides >75% on them.
Hope this helps you further!