Proving correctness of a decryption of a homomorphically summed ciphertext?
For exponential ElGamal this is quite easy if all singe ciphertexts are public (you mentioned they are on a public bulletin board). Lets call $(c_1,c_2)=(g^my^r,g^r)$ the ciphertext corresponding to the sum $m$ of all single encrypted messages after your homomorphic summing (with $y=g^x$ being the public key). The decrypting party simply provides a non-interactive proof of knowledge (signature of knowledge - $SoK$) of the private key $x$ (denoted $\alpha$ below), i.e.,: $$\pi \gets SoK\{(\alpha): c_1=g^mc_2^\alpha ~~\land~~y=c_2^\alpha \}$$ 
along with $m$ (this $SoK$ can be efficiently realised by converting the respective sigma-protocol to a non-interactive proof using Fiat-Shamir). Everybody can now check if homomorphically adding all ciphertexts yields $(c_1,c_2)$ and taking $(c_1,c_2)$ as well as $m$ and $y$ the proof $\pi$ verifies. If all this works out, then everybody will be convinced that the decrypting party behaves honest.

If you have a few million possibilities you can either use a pre-computed lookup table, brute force or by using some suitable, more sophisticated method to compute discrete logarithms, like Pollards lambda method (since you know where to search). Whats more suitable for you depends on your setting, i.e., how resource constrained are your entities, group setting, etc.

You may use a similar approach for any other additively homomorphic encryption scheme (such as Paillier).