Text classification with thousands of output classes in Keras
The ratio of number of examples to number of classes is not large. There are few classes which have high number of occurrences (from the second graph) and the distribution seems to be following power law. 

In such cases, I'll advise the following strategy,


Sort your tags by number of occurrences and discard tags which occur very few number of times. This will make the problem more tractable.
You can benchmark the accuracy that you get from classical machine learning techniques. Many classical methods support multilabel output, you can check the documentation of support in scikit-learn library here.
You can do a mix of unsupervised learning and nearest neighbours approach. For example, learn doc2vec embeddings on your data including tags and suggest tags from nearest matching document for a new input. The number of documents is small by doc2vec standards and you will need careful tuning of doc2vec parameters. 
With neural networks, you can use more suitable loss functions like multilabel soft margin loss.


I'd advise you start with classical techniques to first benchmark the potential accuracy.