Can You Be Fired For Being Hungover? Probably. (So what is next?)

Your question is more a legal one than a mental health one, and I don't know what state you live in so I can't be precise in my answer -- but yes, unfortunately in most states you can be fired for any reason.  I would definitely consult a lawyer if you think this is not the case where you are.

Even in states that are not 'right to work' states, any behavior that interferes with your ability to do your job can lead to firing. You may feel that you work 'well enough' when you are hungover, but your boss may have had a different belief. 

Alcoholism is a disease. It is a treatable disease, and the treatment is highly successful. Like other diseases such as diabetes and heart disease that have a lifestyle component, you have to change your behavior to get better. I'm sure you are aware of this and are doing everything you can.

My favorite definition of addiction is W.A.R.T: With Addiction Repeated Troubles. These troubles can include things like losing jobs and relationships, having physical symptoms such as hangovers and trembling hands and ulcers and liver damage, having legal issues related to the substance, etc. You are aware that you have a problem, and that is a great first step. 

I am glad you are going to AA and taking your Paxil. I worry that your Paxil may be being undermined, however, if you are still drinking. You might want to talk to your psychiatrist or GP about this and ask about one of the new drugs out there that can help you quit drinking, so that you can get the full benefit of your anti-depressant.

When I worked in substance abuse, one of the cues that told us that someone would benefit from residential treatment was when despite working hard on quitting (as you say you are, and I believe you are or you wouldn't be reaching out) they cannot stay sober on their own. I am not saying for sure that you need residential addiction treatment, but it is definitely something to consider at this point. 

One important point I would like to bring up that you might already know is that alcohol is a depressant. When you drink, you actually make your depressive symptoms worse, even though it might not feel like it when you first start drinking. 

In addition to the Paxil and the AA, if you can do it you would probably get a lot out of therapy. Be sure to do a bit of 'shopping' and pick a therapist you feel you can work with. Someone who has worked with people who have both addiction and depression is a good choice. 

Keep working hard like you are doing now, and eventually you will beat this disease. The only way it wins is if you stop trying. Good luck to you!