Can't update or upgrade Homebrew

It's asking you to unshallow both homebrew-core and homebrew-cask with:

git -C "/usr/local/Homebrew/Library/Taps/homebrew/homebrew-core" fetch --unshallow
git -C "/usr/local/Homebrew/Library/Taps/homebrew/homebrew-cask" fetch --unshallow

Nothing worked with me until I did:

cd /usr/local/Homebrew/Library/Taps/homebrew/
rm -rf homebrew-core
git clone https://github.com/Homebrew/homebrew-core.git

Seems that is has been a change in the Homebrew policy and there is not going to be a shallow clone any more.

The correct answer is unshallow, as requested —see Eric3 answer— or install it again, which is going to produce a unshallow / regular copy of the repo.