The paper that appears to have introduced the term "softmax" is Training Stochastic Model Recognition Algorithms as Networks can Lead to Maximum Mutual Information Estimation of Parameters (1989, NIPS) by John S. Bridle.
As a side note, the softmax function (with base $b = e^{-\beta}$)
$$\sigma (\mathbf {z} )_{i}={\frac {e^{-\beta z_{i}}}{\sum _{j=1}^{K}e^{-\beta z_{j}}}}{\text{ for }}i=1,\dotsc ,K {\text{ and }}\mathbf {z} =(z_{1},\dotsc ,z_{K})\in \mathbb {R} ^{K}$$
is very similar to the Boltzmann (or Gibbs) distribution
$$ p_i=\frac{e^{- {\varepsilon}_i / k T}}{\sum_{j=1}^{M}{e^{- {\varepsilon}_j / k T}}} $$
which was formulated by Ludwig Boltzmann in 1868, so the idea and formulation of the softmax function is quite old.