Modeling politeness across cultures helps to improve intercultural communication by uncovering what is considered appropriate and polite. We study the linguistic features associated with politeness across US English and Mandarin Chinese. First, we annotate 5,300 Twitter posts from the US and 5,300 Sina Weibo posts from China for politeness scores. Next, we develop an English and Chinese politeness feature set, `PoliteLex'. Combining it with validated psycholinguistic dictionaries, we then study the correlations between linguistic features and perceived politeness across cultures. We find that on Mandarin Weibo, future-focusing conversations, identifying with a group affiliation, and gratitude are considered to be more polite than on English Twitter. Death-related taboo topics, lack of or poor choice of pronouns, and informal language are associated with higher impoliteness on Mandarin Weibo compared to English Twitter. Finally, we build language-based machine learning models to predict politeness with an F1 score of 0.886 on Mandarin Weibo and a 0.774 on English Twitter.