A razão pela qual sua primeira linha funciona no OSX e não no Ubuntu, é provável porque sh é bash no OSX. $$RANDOM
já está expandido no momento em que o bash -c começa a executá-lo, já que você usou ""
quotes. Então você provavelmente quer isso:
RANDOM := $(shell bash -c 'echo $$RANDOM')
Pessoalmente, eu provavelmente iria com o awk. Algo como
awk 'BEGIN{srand();printf("%d", 65536*rand())}'