Etymologically, yes. Practically, not any more. "Should" should be considered a separate modal verb in modern English. It has even got its own past tense forms, e. g. "Should have done" vs. "should do".
Similarly, "sollten" should not be considered the past tense of "sollen" any more. (Actually, "Ich weiß" used to be the past tense form of "Ich wisse", too! But it is now treated as a present tense form, for practical reasons, not etymological reasons. "Ich wusste" was indeed a new invention after this verb form shift!) The past tense of "sollen tun" is "haben sollen tun". "Sollten" is now used as the subjunctive mood form of "sollen". It forms its own past tense: "hätten sollen tun" (present: "sollten tun").
One of the uses of the subjective mood (Konjunctive II) in German is to express politeness or a suggestion. "Wir sollten jetzt gehen" is more polite than "Wir sollen jetzt gehen". English is similar: "I'd like some coffee" is more polite than "I want coffee". Here, "'d" is a contraction of "would" and the expression "would like" is the subjunctive mood form of "like".
Now that I'm thinking about it, "should" is a bit of an odd word in English. It can be used for all three tenses (past, present & future) pretty much as-is. Even your "We should do that differently." could be all three as written, although it's more explicit if you add helper words like "have".
Come to DL to learn German, start pondering the mysteries of one's native language too...