A direct estimation of salt-mediated potential of mean force (PMF) between spherical micelles of cationic surfactants is obtained for the first time using molecular dynamics (MD) simulations. Coarse-grained (CG) potentials benchmarked in an earlier study [Langmuir, 2011, 27(11), 6628-6638] are used to model a binary system of cetyltrimethylammonium chloride (CTAC) surfactant micelles at varying concentrations of sodium chloride (NaCl) or sodium salicylate (NaSal). The shape and structure of micelles are not subject to external constraints. NaSal is significantly more efficient in screening the intermicelle repulsive interactions shown by the PMF compared to NaCl due to a stronger binding of salicylate counterions to the micelle corona. Upon contact with each other, the micelles coalesce in the presence of NaSal to form a cylindrical structure which is stabilized by the adsorbed salicylate anions. Comparison of the PMF with Derjaguin-Landau-Verwey-Overbeek (DLVO) potentials shows qualitative agreement, while the magnitude of PMF is significantly greater than that of the DLVO potentials. To understand this discrepancy, PMF is evaluated by turning off (a) long-ranged electrostatic interactions and (b) solvent polarizability. The above effects are shown to play an important role in determining the solvent-mediated and ion-correlated interactions between the two micelles, which are not explicitly captured by mean-field double layer theories such as DLVO.