> Do they have to pay more license fees to include English subtitles?

Yes. I asked the customer service in Japan and they told me that subtitles are licensed separately.