After upgrading to macOS Sierra (10.12), I experienced some breakage of some packages. I looked into imagemagick specifically. From the error messages it looked like zlib wasn't being linked in. Running brew install imagemagick --debug --verbose, and inspecting config.log I saw confirmation that the configure script did not find any zlib to link in.
It's my first time with anything close to homebrew internals, but from the diagnostic messages I ran across, I noticed references to pkgconfig and missing configuration. Looking into /usr/local/Library/ENV/pkgconfig I noticed there was one directory for every OS X release up to 10.11. Nothing for 10.12. I created a 10.12 directory and copied zlib.pc over, and TADA, brew install imagemagick installed again without any errors.
The ENV/pkgconfig directory for 10.11 contains a few more files (libcurl, libexslt, libxml, libxslt, sqlite3) and may typically contain more stuff depending on what users have installed I'm guessing. This just as a hint to users experiencing similar breakage (I'm sure zlib, curl and libxml is frequently used).
Hopefully this can help users with some simple workarounds until this gets fixed in the proper places. Since I know very little about homebrew internals I will not be submitting a PR just yet, but hopefully this information can still be useful for somebody. Best case this is just a fix in the pkg-config formula.
I'm working on it. Give me a bit. 10.12 is still _extremely_ new.
Most helpful comment
https://github.com/Homebrew/brew/commit/cc10c632a8c2803b7e62a37c9490beca8fb48128