The Hebrew of Psalm 146:1 is הלל - hll - which gives rise to vocalizations like "Halleluiah". The Septuagint inserts the word αἰνέω (aineō) here, also found in:
And again, Praise the Lord, all ye Gentiles; and laud him, all ye people (Romans 15:11 KJV)
which in turn is quoting Psalm 116 (LXX; Psalm 117 in the Masoretic Text). I think here the word means pretty much what our English word "praise" means, as explained in another answer.
The word used in Romans 12:1 is λατρεία (latreia) and although translated as "worship" by the ESV and other modern editions, really means something more like "service". In the King James, Romans 12:1 is translated:
I beseech you therefore, brethren, by the mercies of God, that ye present your bodies a living sacrifice, holy, acceptable unto God, which is your reasonable service.
Other occasions in which this word arises are:
They shall put you out of the synagogues: yea, the time cometh, that whosoever killeth you will think that he doeth God service (John 16:2 KJV)
Who are Israelites; to whom pertaineth the adoption, and the glory, and the covenants, and the giving of the law, and the service of God, and the promises (Romans 9:4)
Then verily the first covenant had also ordinances of divine service, and a worldly sanctuary (Hebrews 9:1)
Now when these things were thus ordained, the priests went always into the first tabernacle, accomplishing the service of God (Hebrews 9:6)
If one is following Scripture, some confusion can arise, I think, in trying to understand the deeper meaning of English words in our translations, since the same English word might translate many different Greek (or Hebrew or Aramaic) words. "Worship" is one of these cases, I think. In the King James Version, for example, "worship" is used to translate 5 other unique Greek words (some verbs, some nouns), each of which means something slightly different:
προσκυνέω (proskyneō; appears 60 times in the NT)
Saying, Where is he that is born King of the Jews? for we have seen his star in the east, and are come to worship him (Matthew 2:2)
σέβω (sebō; 10 appearances in the NT)
Howbeit in vain do they worship me, teaching for doctrines the commandments of men (Mark 7:7)
δόξα (doxa; 151 appearances in the NT)
But when thou art bidden, go and sit down in the lowest room; that when he that bade thee cometh, he may say unto thee, Friend, go up higher: then shalt thou have worship in the presence of them that sit at meat with thee (Luke 14:10)
εὐσεβέω (eusebeō; 2 appearances in the NT)
For as I passed by, and beheld your devotions, I found an altar with this inscription, TO THE UNKNOWN GOD. Whom therefore ye ignorantly worship, him declare I unto you (Acts 17:23).
ἐθελοθρησκία (ethelothrēskia; 1 appearance in the NT)
Which things have indeed a shew of wisdom in will worship, and humility, and neglecting of the body; not in any honour to the satisfying of the flesh (Colossians 2:23).
To complicate matters further, ambiguities exist in the opposite direction: the same Greek word is translated with different English words. The ESV, for example, translates latreia (Romans 12:1) elsewhere as "service" (John 16:2) and "ritual duties" (Hebrews 9:6). Similarly, the ESV translates proskyneō generally as "worship" (e.g. Matthew 2:2), but also as "kneel before" (Matthew 8:2), "implore" (Matthew 18:26), and "kneel down in homage" (Mark 15:19).