Proving uniqueness
You can prove that the elements are unique in $O(m)$ time and space by pre-sorting them and then giving a zero-knowledge proof that they are in sorted order. Details follow.
Assume the elements of $\Sigma$ are integers in the range $[0,K-1]$, where $K$ is a constant chosen in advance and made public. Pick a large prime $p$ and a group element $g \in (\mathbb{Z}/p\mathbb{Z})^*$ of prime order $q$, such that $q > 2K$. The scheme is:
First, sort the elements of $\Sigma$, so $\sigma_1 < \sigma_2 < \cdots < \sigma_m$. Next, commit to all the elements, using a discrete log based commitment scheme with generator $g$; for instance, you might use Pedersen commitments. Finally, prove that the elements are in sorted value, i.e., that $\sigma_i < \sigma_{i+1}$ holds for all $i$.
You can prove they are in sorted order using a range proof for discrete logs: for all $i$, you show that $\sigma_i \in [0,K-1]$, and you show that $\sigma_{i+1} - \sigma_i \in [1,K-1]$ (again, considering the $\sigma_i$'s as integers). To prove that $\sigma_{i+1} - \sigma_i \in [1,K-1]$, it suffices to prove that $d_i = \sigma_{i+1} - \sigma_i \bmod q$ is in the range $[1,K-1]$: since you've proven that each $\sigma_i$ is in $[0,K-1]$, and since $q \ge 2K$, there can be no wrap-around modulo $q$. All that remains is how to describe that each $d_i$ is in the specified range.
One standard way to do a range proof is to express each $d_i$ in binary, i.e.,
$$d_i = \sum_j b_{i,j} 2^j.$$
Then you commit to all the $b_{i,j}$'s, use the homomorphic property of commitments to show that the $b_{i,j}$'s are consistent with the $d_i$'s (i.e., that the equation above holds), and show that $b_{i,j} \in \{0,1\}$ for each $i,j$. Of course, you can prove that the $d_i$'s were computed correctly by using the homomorphic property of discrete log-based commitment schemes: given the commitments $C(\sigma_{i+1})$ and $C(\sigma_i)$, anyone can compute a commitment $C(d_i)=C(\sigma_{i+1}-\sigma_i \bmod q)$ to $d_i$, even without knowing $\sigma_i,\sigma_{i+1}$.
When using this method of range proofs together with the idea above, it will give you a valid proof that the elements $\sigma_1,\dots,\sigma_m$ are mutually disjoint.
Proving it is a subset
You can show that $\Sigma \subseteq \Psi$ using the techniques in the paper you mentioned.