To convert from molal to molar, one generally needs to know the density of solution as well as the formula weight of solute.  Suppose there is a single solute $x$ in water, and that $x$ has a formula weight of $f_x$ g/mol.  Suppose also that the solution of $x$ has a density of of $\rho$.

Let the molarity of $x$ in the solution be $C_x$ mol/L.  Then:

 - the mass concentration of $x$ in g/L is $C_x f_x$.  
 - the weight _fraction_ of $x$ in grams of $x$ per _total_ gram of solution is thus $w_x = \frac{C_x f_x}{\rho}$.  The weight fraction $w_x$ must be a number between 0 and 1.
 - The weight _ratio_ of $x$ in grams of $x$ per gram of water is $\frac{\frac{C_x f_x}{\rho}}{1-\frac{C_x f_x}{\rho}} = \frac{w_x}{1-w_x}$.
 - The molality is simply the weight ratio divided by the formula weight, $\frac{1000}{f_x}\frac{\frac{C_x f_x}{\rho}}{1-\frac{C_x f_x}{\rho}}$.  The factor of 1000 is because molality is moles per kg of solvent, not moles per g.
 - That last expression can be written as  $\frac{1000}{f_x}\frac{\frac{C_x f_x}{\rho}}{1-\frac{C_x f_x}{\rho}} = \frac{1000}{f_x} \frac{w_x}{1-w_x}$

This last formula shows that molality values will always be higher than molarity values.  Because $w_x$ has to be between zero and 1, then the molality formula will divide by a smaller number than then molarity formula.  One molar water "dissolved" in water (say we are dissolving distilled water in tap water, or dissolving isotopically labeled water into regular water) has a molality of around 1.02.

> My approach is:

>- Convert 1M into molality and then compare if it is less or more than 1m. (?)

Good approach.

>- The density of water is 1kg per L.

True, but as noted in the comments, the density of solutions in water can be either higher or lower than the density of pure water.

>- When solute is added to it, density would definitely increase(?)

Not necessarily true.

> - And therefore 1L of that solution will weigh more than 1 kg.

Not true, and this is the point where I think your logic mislead you.  To make one liter of a 1 molar solution, _less than_ one liter of pure water is usually required.  This is because part of the liter of solution is taken up by solute.  So not all of the liter needs to come from pure water.  And since water has a density of 1 kg/L, if we need _less than_ one liter of pure water, we need less than 1 kg of pure water.  This then means that our one mole of solute is being dissolved by _less_ than kg of solvent: thus ***the molality of a one-molar solution is greater than one.***

The neat thing is that this is true regardless of the density or formula weight of the species being considered.