Does a distance matrix have to be Euclidean in order to be clustered by an average-linking algorithm (UPGMA)?
While you can modify any algorithm as you see fit, in its pure form UPGMA has the following underlying assumptions at work:

UPGMA (Unweighted Pair-Group Method with Averages), arithmetic average - the average distance between elements of each cluster (weighted by the number of elements).

For example, (AB) and C+(DE) = (55+3x45)/3 = 63.33

Additional Comparative Algorithmic Context

Below is a list of algorithms and their general framework as it relates to each algorithm:


SINGLE (Single-link method) – brings together the closest elements.
WPGMA (Weighted Pair-Group Method with Averages), arithmetic average (not weighted by the number of elements). 
WPGMC (Weighted Pair-Group Method with Centroid Average), centroid average (assumes dissimilarity).
WPGMS (Weighted Pair-Group Method with Spearman Average), Spearman's average (assumes correlation).


Reference for Modifying UPGMA

The paper below is a wonderful resource for "what-if" scenarios as it relates to UPGMA:

Vavrek, M. J. (2016). A comparison of clustering methods for biogeography with fossil datasets. PeerJ, 4, e1720. http://doi.org/10.7717/peerj.1720