There is no contradiction. Your relation for attenuation constant $\alpha$ is only valid for good conductors, which, by definition, have $\sigma>>\omega\epsilon$. Therefore, if you want to be accurate, you will also put $\sigma>>\omega\epsilon$ in the loss tanget $\tan\delta$ and get a compatibly large value.
The general case (lossy general medium) is to derive $\alpha$ from the complex propagation constant ($\gamma$) by taking its real part:
$$ \alpha=\Re[\gamma]=\Re[i\omega\sqrt{\mu\epsilon_{\text{complex}}}]=\Re\left[i\omega\sqrt{\mu\epsilon(1-i\tan\delta)}\right] = \Re\left[i\omega\sqrt{\mu\epsilon(1-i\frac{\sigma}{\omega\epsilon})}\right] \ \ \ \ \ \ \ (1).$$
As you can see from (1), if we take the limit of high frequency, $\omega\epsilon>>\sigma$, the loss tangent vanishes and $\gamma$ becomes purely imaginary, leaving $\alpha$ to vanish, too (which makes sense).
Equation (1) only reduces to your equation ($\alpha\rightarrow\sqrt{\omega \mu \sigma/2}$) in the limit $\sigma>>\omega\epsilon$, in which case the loss tangent is large anyway (by definition) and having high frequency will also give you high $\alpha$ loss (so both will be large), to reflect the losses in a good conductor, and eventually leads us the concept of "skin depth", in which energy is confined to a thinner layer in the conductor's outer surface, at higher frequencies, causing more losses. Note, however, that at low frequencies, the conductor's loss is not as bad (negligible skin effect), even though its loss tangent is high. Therefore, $\tan\delta$ as a material constant should not be confused with propagation-related constants, like $\alpha$.
Indeed, the more general definition of loss tangent in a medium (with complex permittivity $\epsilon=\epsilon'-i\epsilon''$ and conductivity $\sigma$) is being the ratio of the imaginary part of the total displacement current to its real part [see Pozar]:
$$ \text{curl} H=i\omega D + J=i\omega\epsilon E+\sigma E= i\omega\epsilon' E+(\omega\epsilon''+\sigma)E=i\omega\left[\epsilon'-i(\epsilon''+\frac{\sigma}{\omega})\right]E \equiv i\omega D_{\text{tot}}$$
$$ \Rightarrow \tan\delta =\frac{\text{imaginary part of}\ D_{\text{tot}}}{\text{real part of}\ D_{\text{tot}}}=\frac{\omega\epsilon''+\sigma}{\omega\epsilon'}.$$
Usually we consider the losses due to conductivity ($\sigma$) to be indistinguishable from losses due to dielectric damping ($\epsilon''$) and the loss tangent changes with frequency. More purely, however, if we had only $\epsilon''$ (no conductivity), then $\tan\delta$ would be a true constant (independent of frequency) and it becomes clearer that it should not be confused with propagation paramaters. In practice, a middle scenario is often seen; the frequency dependence of loss tangent of a material is not always a straightforward relation.
