Why is openssl complaining that my certificate chain is self-signed?

First, it is quite correct for a TLS/SSL server to send the intermediate aka chain cert(s) but not the root cert; see rfc 5246 sec 7.4.2 or the slightly more verbose version in rfc 8446 sec 4.4.2.

As Z.T. mostly-correctly commented, -verify is the default for s_client (you don't need to specify it) and if you don't specify -CAfile and/or -CApath by default (except for bugs in some obsolete versions) it uses a default truststore, configured at compile time, which can include either a single file with concatenated PEM certs or a directory containing separate PEM files with names or links using truncated subject hashes usually created by c_rehash (add) or, as commented, manually determined with x509 -hash; see the man page for verify(1ssl) on your system or on the web. OpenSSL itself doesn't provide the root certs that go in such a truststore; if you are using a distro or other packaged version, the builder usually configures OpenSSL to use a set of root certs provided by the distro or package. (On distros I know, this distro-provided truststore is also used for other software including NSS, GNUtls, and Java; see below.) If you (or someone) built OpenSSL by hand, you have to do this yourself. Since you are not getting a verify error on public servers, your build presumably is using a truststore that has (at least some) public CA's preinstalled; you can see where this is with openssl version -d (plus the hardcoded names cert.pem and/or certs).

You can add your root or other anchor (see below) to this default truststore, or use -CAfile and/or -CApath to specify a custom one containing your own root(s) or anchor(s). On the distros I know, and probably others, you should NOT hand-modify the default files because they are automatically generated by a process that also sets the truststores used by other software such as NSS, GNUtls, and Java; these need to contain the same data (certs) but in different formats. Instead see e.g. man update-ca-trust for RedHat family or man update-ca-certificates for Debian family.

OpenSSL will use an intermediate (aka chain) cert or certs in the truststore to build the cert chain if needed, i.e. if not sent by the server (in violation of the RFC, but many do that), but historically it will only accept a chain -- either fully received from the server or (partly) built from the local truststore -- if it ends at a root that is in the local truststore. For recent versions, namely 1.0.2 up but only documented since 1.1.0, there is an option -partial_chain which does accept a chain ending in an intermediate (non-root) that is in the local truststore.