By considering correlations between classical orbits we derive semiclassical expressions for the decay of the quantum fidelity amplitude for classically chaotic quantum systems, as well as for its squared modulus, the fidelity or Loschmidt echo. Our semiclassical results for the fidelity amplitude agree with random matrix theory (RMT) and supersymmetry predictions in the universal Fermi-golden rule regime. The calculated quantum corrections can be viewed as arising from a static random perturbation acting on nearly self-retracing interfering paths, and hence will be suppressed for time-varying perturbations. Moreover, using trajectory-based methods we show a relation, recently obtained in RMT, between the fidelity amplitude and the cross-form factor for parametric level correlations. Beyond RMT, we compute Ehrenfest-time effects on the fidelity amplitude. Furthermore our semiclassical approach allows for a unified treatment of the fidelity, both in the Fermi-golden rule and Lyapunov regimes, demonstrating that quantum corrections are suppressed in the latter.