I’ve having the same issues davemf was having. I’ve installed gcc-linaro-aarch64-linux-gnu-4.9-2014.09_linux in /opt/toolchains on Ubuntu 16.04.
tott@tott-VirtualBox:~/aosp/uboot$ make CROSS_COMPILE=/opt/toolchains/gcc-linaro-aarch64-linux-gnu-4.9-2014.09_linux/bin/aarch64-linux-gnu- kvim2_defconfig
HOSTCC scripts/basic/fixdep
/bin/sh: 1: cc: not found
scripts/Makefile.host:91: recipe for target ‘scripts/basic/fixdep’ failed
make[2]: *** [scripts/basic/fixdep] Error 127
/home/tott/aosp/uboot/Makefile:395: recipe for target ‘scripts_basic’ failed
make[1]: *** [scripts_basic] Error 2
Makefile:147: recipe for target ‘sub-make’ failed
make: *** [sub-make] Error 2