How does `std::mem::swap` work?

The function does actually make a copy internally: here is its source extracted from the documentation:

pub fn swap<T>(x: &mut T, y: &mut T) {
    unsafe {
        // Give ourselves some scratch space to work with
        let mut t: T = uninitialized();

        // Perform the swap, `&mut` pointers never alias
        ptr::copy_nonoverlapping(&*x, &mut t, 1);
        ptr::copy_nonoverlapping(&*y, x, 1);
        ptr::copy_nonoverlapping(&t, y, 1);

        // y and t now point to the same thing,
        // but we need to completely forget `t`
        // because it's no longer relevant.
        forget(t);
    }
}

The previous answer is correct in semantics, but outdated in exact details.

Logically, swapping two values works by reading value A into a temporary location, copying B on top of A, then writing the temporary value back into B. There is a brief period where the same value exists twice in memory. This is why the implementation of these functions requires unsafe code, as only a human can guarantee that Rust's safety requirements are upheld.

As of Rust 1.43.0, mem::swap is implemented as:

pub fn swap<T>(x: &mut T, y: &mut T) {
    // SAFETY: the raw pointers have been created from safe mutable references satisfying all the
    // constraints on `ptr::swap_nonoverlapping_one`
    unsafe {
        ptr::swap_nonoverlapping_one(x, y);
    }
}

swap_nonoverlapping_one is private, but its implementation is:

pub(crate) unsafe fn swap_nonoverlapping_one<T>(x: *mut T, y: *mut T) {
    // For types smaller than the block optimization below,
    // just swap directly to avoid pessimizing codegen.
    if mem::size_of::<T>() < 32 {
        let z = read(x);
        copy_nonoverlapping(y, x, 1);
        write(y, z);
    } else {
        swap_nonoverlapping(x, y, 1);
    }
}

You can see the documentation for ptr::copy_nonoverlapping and ptr::swap_nonoverlapping. The latter is basically a highly-optimized version of copying for larger values.